BZOJ2095 POI2010 Bridges

Description

YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。

Input

输入：第一行为两个用空格隔开的整数n（2<=n<=1000），m(1<=m<=2000)，接下来读入m行由空格隔开的4个整数a，b(1<=a,b<=n,a<>b)，c，d(1<=c,d<=1000)，表示第i+1行第i座桥连接小岛a和b，从a到b承受的风力为c，从b到a承受的风力为d。

Output

输出：如果无法完成减肥计划，则输出NIE，否则第一行输出承受风力的最大值（要使它最小)

Sample Input

4 4

1 2 2 4

2 3 3 4

3 4 4 4

4 1 5 4

Sample Output

首先看到最大风力最小就知道是二分

然后我们把图建出来发现是有些边有向，有些边无向，所以就是混合图欧拉回路

有关混合图欧拉回路的求解，可以看一看这篇文章



#include<bits/stdc++.h>

using namespace std;

#define N 2010

#define INF 0x3f3f3f3f

struct Edge{int u,v,cap,flow;};

struct Dinic{

    int s,t,d[N];bool vis[N];

    vector<int> G[N];

    vector<Edge> E;

    void init(int _n){

        E.clear();

        for(int i=0;i<=_n;i++)G[i].clear();

    }

    void add(int u,int v,int w){

        E.push_back((Edge){u,v,w,0});

        E.push_back((Edge){v,u,0,0});

        int m=E.size();

        G[u].push_back(m-2);

        G[v].push_back(m-1);

    }

    bool bfs(){

        static queue<int> q;

        memset(vis,0,sizeof(vis));

        q.push(s);d[s]=0;vis[s]=1;

        while(!q.empty()){

            int u=q.front();q.pop();

            for(int i=0;i<G[u].size();i++){

                Edge e=E[G[u][i]];

                if(!vis[e.v]&&e.cap>e.flow){

                    vis[e.v]=1;

                    d[e.v]=d[e.u]+1;

                    q.push(e.v);

                }

            }

        }

        return vis[t];

    }

    int dfs(int u,int a){

        if(!a||u==t)return a;

        int flow=0;

        for(int i=0;i<G[u].size();i++){

            Edge &e=E[G[u][i]];

            if(d[e.v]!=d[u]+1)continue;

            int f=dfs(e.v,min(a,e.cap-e.flow));

            e.flow+=f;

            E[G[u][i]^1].flow-=f;

            flow+=f;

            a-=f;

            if(!a)break;

        }

        if(!flow)d[u]=0;

        return flow;

    }

    int Maxflow(){

        int flow=0;

        while(bfs())flow+=dfs(s,INF);

        return flow;

    }

}dinic;

int n,m;

int U[N],V[N],C[N],D[N];

int in[N],out[N];

bool check(int val){

    for(int i=1;i<=n;i++)in[i]=out[i]=0;

    dinic.init(n+1);

    int sum=0;

    for(int i=1;i<=m;i++){

        if(C[i]<=val)out[U[i]]++,in[V[i]]++;

        if(D[i]<=val)dinic.add(V[i],U[i],1);

    }

    for(int i=1;i<=n;i++)if(abs(in[i]-out[i])&1)return 0;

    for(int i=1;i<=n;i++){

        int tmp=in[i]-out[i];

        if(tmp>0)sum+=tmp>>1;

        if(tmp>0)dinic.add(0,i,tmp>>1);

        if(tmp<0)dinic.add(i,n+1,(-tmp)>>1);

    }

    return dinic.Maxflow()==sum;

}

int main(){

    scanf("%d%d",&n,&m);

    dinic.s=0;dinic.t=n+1;

    int L=INF,R=0,ans=-1;

    for(int i=1;i<=m;i++){

        scanf("%d%d%d%d",&U[i],&V[i],&C[i],&D[i]);

        if(C[i]>D[i])swap(C[i],D[i]),swap(U[i],V[i]);

        L=min(L,C[i]);

        R=max(R,D[i]);

    }

    while(L<=R){

        int mid=(L+R)>>1;

        if(check(mid))R=mid-1,ans=mid;

        else L=mid+1;

    }

    if(ans==-1)printf("NIE");

    else printf("%d",ans);

    return 0;

}

YYD