图论杂题

P5304 [GXOI/GZOI2019]旅行者

一个套路是如果要在某些点里找两个满足某条件可以二进制分组，一定有一次两个点分到不同组里。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct node{
    int v,w,next;
}edge[500010];
int n,m,k,t,S,T,head[100010],a[100010],tmp[100010];
bool v[100010];
long long ans,dis[100010];
void add(int u,int v,int w){
    edge[++t].v=v;edge[t].w=w;
    edge[t].next=head[u];head[u]=t;
}
struct stu{
    int x;long long w;
    bool operator<(const stu&s)const{
        return w>s.w;
    }
};
priority_queue<stu>q;
void dijkstra(int st){
    for(int i=1;i<=n+1;i++)dis[i]=__LONG_LONG_MAX__,v[i]=false;
    q.push({st,0});dis[st]=0;v[st]=false;
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(!v[x]){
            v[x]=true;
            for(int i=head[x];i;i=edge[i].next){
                if(dis[edge[i].v]>dis[x]+edge[i].w){
                    dis[edge[i].v]=dis[x]+edge[i].w;
                    if(!v[edge[i].v])q.push({edge[i].v,dis[edge[i].v]});
                }
            }
        }
    }
}
int main(){
    int tim;scanf("%d",&tim);
    while(tim--){
        scanf("%d%d%d",&n,&m,&k);S=0;T=n+1;t=0;
        ans=__LONG_LONG_MAX__;
        for(int i=1;i<=m;i++){
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        for(int i=0;i<k;i++)scanf("%d",&a[i]);
        int ret=t;
        for(int i=1;i<=n;i++)tmp[i]=head[i];
        for(int i=0;i<=__lg(k);i++){
            t=ret;head[S]=head[T]=0;
            for(int i=1;i<=n;i++)head[i]=tmp[i];
            for(int j=0;j<k;j++){
                if((j>>i)&1)add(S,a[j],0);
                else add(a[j],T,0);
            }
            dijkstra(S);
            ans=min(ans,dis[T]);
        }
        for(int i=0;i<=__lg(k);i++){
            t=ret;head[S]=head[T]=0;
            for(int i=1;i<=n;i++)head[i]=tmp[i];
            for(int j=0;j<k;j++){
                if((j>>i)&1)add(a[j],T,0);
                else add(S,a[j],0);
            }
            dijkstra(S);
            ans=min(ans,dis[T]);
        }
        for(int i=0;i<=n+1;i++)head[i]=0;
        printf("%lld\n",ans);
    }
    return 0;
}

CF1163F Indecisive Taxi Fee

首先显然从 \(1-n\) 和 \(n-1\) 建最短路树，保证最短路树上 \(1-n\) 的最短路相同。然后对某条修改的边开始讨论。

1. 不在最短路上：直接强制选这条边，拼接就行。
2. 在最短路上：首先一个方案是选这条边。还有一个是强制不选这条边，这个不太好搞。

一个结论是每条这样不经过某条边的路径一定是经过原最短路的一个前缀，再经过一些不在原最短路上的边，再进过原最短路的一个后缀组成的。所以每条不在最短路上的边可以更新一个前缀到一个后缀的答案。这个前缀和后缀可以最短路树上搜一遍。然后线段树即可。

看起来就很难写，代码找joke3579。

P5590 赛车游戏

转换思路，与其设置边权使路径长度相等，不如设置路径长度去拟合边权的限制。

这个边权配合最短路一定满足 \(1\le 0dis_v-dis_u\le 9\)。很差分约束。注意不能考虑不在 \(1-n\) 路径上的边，要不然会算错。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
struct node{
    int v,w,next;
}edge[10010];
int n,m,t,head[1010],u[2010],v[2010],cnt[1010],dis[1010];
void add(int u,int v,int w=0){
    edge[++t].v=v;edge[t].w=w;edge[t].next=head[u];head[u]=t;
}
bool vis[1010],belong[1010];
bool dfs(int x){
    vis[x]=true;
    if(x==n)return belong[x]=true;
    for(int i=head[x];i;i=edge[i].next){
        if(!vis[edge[i].v])dfs(edge[i].v);
        if(belong[edge[i].v])belong[x]=true;
    }
    return belong[x];
}
queue<int>q;
bool spfa(int st){
    q.push(st);dis[st]=0;vis[st]=true;
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=false;
        for(int i=head[x];i;i=edge[i].next){
            if(dis[edge[i].v]>dis[x]+edge[i].w){
                dis[edge[i].v]=dis[x]+edge[i].w;
                cnt[edge[i].v]=cnt[x]+1;
                if(cnt[edge[i].v]>n)return false;
                if(!vis[edge[i].v])q.push(edge[i].v),vis[edge[i].v]=true;
            }
        }
    }
    return true;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i]);
    }
    if(!dfs(1)){
        puts("-1");return 0;
    }
    t=0;
    for(int i=1;i<=n;i++)head[i]=0,vis[i]=false,dis[i]=0x3f3f3f3f;
    for(int i=1;i<=m;i++){
        if(belong[u[i]]&&belong[v[i]])add(u[i],v[i],9),add(v[i],u[i],-1);
    }
    for(int i=1;i<=n;i++)add(0,i,0);
    if(!spfa(0)){
        puts("-1");return 0;
    }
    printf("%d %d\n",n,m);
    for(int i=1;i<=m;i++){
        printf("%d %d ",u[i],v[i]);
        int d=dis[v[i]]-dis[u[i]];
        if(d>0&&d<10)printf("%d\n",d);
        else puts("1");
    }
    return 0;
}

P4926 [1007]倍杀测量者

经典题。取对数二分答案就行了。

CF888G Xor-MST

某个姓 B 的算法的思想可以解决这一类数据范围比较大的完全图最小生成树问题。

首先先去个重。然后显然可以在 01trie 上从低到高位考虑合并两个连通块。这时候 01trie 就变成了决策树。

dfs 整棵 trie，搜到一个节点时显然所有子树的节点合并完了。这时候从左子树和右子树暴力找出来一对点合并就行了。启发式合并复杂度显然正确，不启发式也对，因为每个点最多被扫 \(\log(\max(a_i))\) 次。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
int n,cnt=1,a[200010],trie[6000010][2],l[6000010],r[6000010];
long long ans;
void ins(int x,int id){
    int p=1;
    for(int i=30;i>=0;i--){
        int w=(x>>i)&1;
        if(!l[p])l[p]=id;
        r[p]=id;
        if(!trie[p][w])trie[p][w]=++cnt;
        p=trie[p][w];
    }
    if(!l[p])l[p]=id;
    r[p]=id;
}
int query(int x,int val,int dep){
    int w=(val>>dep)&1;
    if(trie[x][w])return query(trie[x][w],val,dep-1);
    else if(trie[x][w^1])return query(trie[x][w^1],val,dep-1)+(1<<dep);
    return 0;
}
long long dfs(int x,int dep){
    if(trie[x][0]&&trie[x][1]){
        int mn=2147483647;
        for(int i=l[trie[x][0]];i<=r[trie[x][0]];i++)mn=min(mn,query(trie[x][1],a[i],dep-1));
        return dfs(trie[x][0],dep-1)+dfs(trie[x][1],dep-1)+mn+(1<<dep);
    }
    if(trie[x][0])return dfs(trie[x][0],dep-1);
    if(trie[x][1])return dfs(trie[x][1],dep-1);
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++)ins(a[i],i);
    ans=dfs(1,30);
    printf("%lld\n",ans);
    return 0;
}

CF51F Caterpillar

首先显然边双缩点。然后考虑选出最多的点被留下。

考虑确定了主链之后怎么保留剩下的点，也就是一堆叶子。容易发现祖先后代不能同时选。那么选所有的叶子就是最优的。

于是保留的点就是链长+叶子个数。链显然选直径。然后没了。

写了一半，写到树的直径吃饭去了，然后就不写了。

CF555E Case of Computer Network

关键结论：边双一定可以定向成 SCC。证明考虑每次选出一个环定向。由于每两个点之间都是边双连通的所以一定可以定出来。然后做完了。

原文地址：http://www.cnblogs.com/gtm1514/p/16912976.html