bzoj2095 bridges 【網絡流判歐拉回路】

題意：

給出一個n個點m條邊的無向圖，每個邊有一正一反兩個權值；

現要從點1出發，對每條邊經過且僅經過一次；

求一種方案使經過的最大權值最小；

(bzoj)輸出這個權值即可；

題解：

最小值最大顯然二分；

二分之後就轉化成了一個判定性問題：求這個圖中是否存在歐拉回路；

而最糟糕的是。。這是混合圖。。。

有向圖的歐拉回路：每個點的入度=出度

無向圖的歐拉回路：每個點的度為偶數；

混合圖的歐拉回路：網絡流！

混合圖與有向圖的差別就在于其中無向邊的方向不一定；

我們先使所有的無向邊固定一個方向；

很明顯，每個點的度一定要是偶數。

但這樣得到的圖未必是一個歐拉圖，因為有的點入度大于出度，有的點出度大于入度；

是以我們需将其調整為每個點的出度等于入度。那麼每個點最終出度入度=（目前出度+入度）/2,然後經計算可得每個點需調整 |（入度-出度）/2| 的邊，但由于調整一個點會影響到另一個點，是以想到了網絡流。

為了調整這裡，我們：

從源點向入度大于出度的點連流量為入度減出度/2的邊；

從入度小于出度向彙點的點連流量為出度減入度/2的邊；

對一條無向邊，連這條邊的方向反向，流量為1的邊；

每流過一條邊，相當于将這條邊反向，兩個點的入度與出度得到調整；

對這個網絡求最大流就調整了盡可能多的無向邊；

檢查是否存在歐拉回路就是查源點彙點所連的邊是否滿流即可；

注意還有一條件是圖連通，用并查集判斷一下就好了；

時間複雜度O(Dinic*logm)；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int getint()
{
    int i=;char c;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())i=(i<<)+(i<<)+c-'0';
    return i;
}

const int N=,M=,INF=;
int n,m,src,des,tot,totin,totout;
int X[M],Y[M],a[M],b[M],que[N];
int in[N],out[N],fa[N],size[N],dis[N];
int first[N],cur[N],next[M],to[M],cap[M];

void add(int x,int y,int z)
{
    next[++tot]=first[x],first[x]=tot,to[tot]=y,cap[tot]=z;
    next[++tot]=first[y],first[y]=tot,to[tot]=x,cap[tot]=;
}

int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y)fa[y]=x,size[x]+=size[y];
}

bool bfs()
{
    for(int i=;i<=des;i++)dis[i]=-,cur[i]=first[i];
    int head=,tail=;
    que[++tail]=src,dis[src]=;
    while(head<tail)
    {
        int u=que[++head];
        for(int e=first[u];e;e=next[e])
        {
            int v=to[e];
            if(dis[v]==-&&cap[e])
            {
                dis[v]=dis[u]+;
                que[++tail]=v;
                if(v==des)return ; 
            }
        } 
    }
    return ;
}

int dinic(int u,int flow)
{
    if(u==des)return flow;
    int res=;
    for(int &e=cur[u];e;e=next[e])
    {
        int v=to[e];
        if(cap[e]&&dis[v]==dis[u]+)
        {
            int delta=dinic(v,min(flow-res,cap[e]));
            cap[e]-=delta,cap[e^]+=delta;
            res+=delta;if(res==flow)break;
        }
    }
    if(res<flow)dis[u]==-;
    return res;
}

int maxflow()
{
    int res=;
    while(bfs())res+=dinic(src,INF);
    return res;
}

bool check(int lim)
{
    memset(in,,sizeof(in));
    memset(out,,sizeof(out));
    memset(first,,sizeof(first));
    tot=,totin=totout=;
    for(int i=;i<=n;i++)fa[i]=i,size[i]=;
    for(int i=;i<=m;i++)
    {
        if(a[i]<=lim&&b[i]<=lim)
        {
            out[X[i]]++,in[Y[i]]++;
            merge(X[i],Y[i]);
            add(Y[i],X[i],);
        }
        else if(a[i]<=lim)
        {
            out[X[i]]++,in[Y[i]]++;
            merge(X[i],Y[i]);
        }
        else if(b[i]<=lim)
        {
            out[Y[i]]++,in[X[i]]++;
            merge(X[i],Y[i]);
        }
    }
    if(size[find()]!=n)return ;
    for(int i=;i<=n;i++)
    {
        if((in[i]+out[i])&)return ;
        if(in[i]==out[i])continue;
        if(in[i]>out[i])
        {
            add(src,i,in[i]-out[i]>>);
            totin+=in[i]-out[i]>>;
        }
        else
        {
            add(i,des,out[i]-in[i]>>);
            totout+=out[i]-in[i]>>;
        }
    }
    if(totin!=totout)return ;
    if(maxflow()==totin)return ;
    else return ;

}


int main()
{
    //freopen("lx.in","r",stdin);
    int l,r,mi,mx;
    n=getint(),m=getint();
    src=n+,des=n+;
    for(int i=;i<=m;i++)
    {
        X[i]=getint(),Y[i]=getint();
        a[i]=getint(),b[i]=getint();
        mi=min(mi,min(a[i],b[i]));
        mx=max(mx,max(a[i],b[i]));
    }
    l=mi,r=mx;
    while(l<=r)
    {
        int mid=l+r>>;
        if(check(mid))r=mid-;
        else l=mid+;
    }
    if(l>mx)cout<<"NIE"<<'\n';
    else cout<<l<<'\n';
    return ;
}