题解 P3511 【[POI2010]MOS-Bridges】

· · 题解

2021.9.28修了求欧拉回路的锅&精简了内容。

statement

有 n(n \leq 1000) 个点和 m(m \leq 20000) 条边，每条边有两个权值，分别表示从 u 到 v 和从 v 到 u 的边权。

求图中的一个欧拉回路，使得回路中的最大边权最小，并输出方案。

（不知道欧拉回路的自行百度）

solution

首先，题目要求最大边权最小的欧拉回路，我们想到二分答案

对于每一个 mid 建出一个图。

图中有有向边和无向边。

欧拉回路有一个性质：每一个点的入度=出度。

我们把每一个点分成入度>出度和入度<出度两类。

建立虚拟源点 S 和汇点 T。

若当前点的入度>出度，则它需要多流入入度-出度的流量才可能满足入度=出度。

若当前点的入度<出度，则它需要多留出出度-入度的流量才可能满足入度=出度。

等等......

这道题还有无向边，

那我们如何处理呢？

其实很简单，对于 u \ v 之间的无向边，先把它定一个方向（下文假设初始是从 u 到 v 的），

再连一条从 v 连 u 之间流量为1的边，相当于我可以反悔。

那么，我们还可以加一个判断：

若有一个点的入度-出度为奇数，则一定无解。

因为改变无向边的方向，该点的入度-出度的值一定还是奇数，即不可能为0，一定无解。

接下来跑最大流，

若源点连向入度>出度的点的流量未满，则说明不存在欧拉回路，因为肯定有点的入度≠出度。

若满足此条件，则此 mid 可行。

当二分结束后，我们得到了最终答案 ans

对于 ans 建出一个有向图

接下来只要找出走的方案就可以了

那如何求呢？

其实就是欧拉回路的板子

P7771 欧拉路径

这里面的题解讲的很清楚。

一些需要注意的地方：

首先要判断图的连通性（用并查集即可），不然会被 Hack ，比如

6 6
1 2 1 1
2 3 1 1
3 1 1 1
4 5 1 1
5 6 1 1
6 4 1 1

但是，孤立点是不用管的，因为欧拉回路只要求经过所有边一次，所以还要判断一下，比如

5 4
1 2 1 1
2 3 1 1
3 4 1 1
4 1 1 1

还要判断是否有边未被加入，不然会被 这个帖子 Hack 。

\Large\text{Code\ time} 
//省略了网络流板子和并查集板子。
#define N 2050
#define M 40050
int deg[N],n,S,T,ALL,m,w1[M],w2[M],u[M],v[M],id[M];
//建图 
bool build(int mid){
    Flow.clear();
    memset(deg,0,sizeof(deg));
    Flow.n=n+2;
    S=n+1;T=n+2;ALL=0;
    for(int i=1;i<=m;++i){
        if(w1[i]<=mid)deg[u[i]]--,deg[v[i]]++;
        if(w2[i]<=mid){
            id[i]=Flow.Top+1;
            Flow.Add(v[i],u[i],1);
        }
    }
    for(int i=1;i<=n;++i)
        if(deg[i]&1)return false;
    for(int i=1;i<=n;++i)//分两类 
        if(deg[i]>0)ALL+=deg[i]/2,Flow.Add(S,i,deg[i]/2);//入度>出度 
        else Flow.Add(i,T,-deg[i]/2);//出度>=入度 
    return true;
}
bool check(int mid){
    if(!build(mid))return false;
    return Flow.dinic(S,T)==ALL;
}
int top;
bool vis[M];
int res[M];
//下面是欧拉回路
void dfs(int x){
    for(int i=head[x];i;i=head[x]){//注意是i=head[x]，不然可以被卡成O(m^2)
        head[x]=i;
        if(vis[e[i].id])continue;
        vis[e[i].id]=1;
        dfs(e[i].to);
        res[++top]=e[i].id;
    }
}
void output(int ans){
    build(ans);
    Flow.dinic(S,T);
    for(int i=1;i<=m;++i){
        if(w1[i]<=ans&&w2[i]<=ans){
            if(Flow.e[id[i]].w==0)add(v[i],u[i],i);
            else add(u[i],v[i],i);
        }else
        if(w1[i]<=ans)add(u[i],v[i],i);
        else if(w2[i]<=ans)add(v[i],u[i],i);
    }
    dfs(1);
    for(int i=top;i>=1;--i)
        printf("%d ",res[i]);
    puts("");
}
bool ok[N],tot;
int main(){
    n=read();m=read();cnt=n;
    int l=1001,r=0,mid,ans=1001;
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        u[i]=read(),v[i]=read(),w1[i]=read(),w2[i]=read();
        ok[u[i]]=1;ok[v[i]]=1;
        Merge(u[i],v[i]);
        if(w1[i]>w2[i]){
            swap(u[i],v[i]);
            swap(w1[i],w2[i]);
        }
        l=min(w1[i],l);r=max(w2[i],r);//防止有边未被加入 
    }
    for(int i=1;i<=n;++i)
        if(!ok[i])++tot;
    if(cnt!=1&&cnt-tot!=1){//不连通 && 排除孤立点 
        puts("NIE");
        return 0;
    }
    while(l<=r){//二分 
        mid=l+r>>1;
        if(check(mid))
            r=mid-1,ans=mid;
        else l=mid+1;
    }
    if(ans==1001){//无解 
        puts("NIE");
        return 0;
    }
    printf("%d\n",ans);
    output(ans);//输出方案 
    return 0;
}