[BZOJ2095][Poi2010]Bridges 二分+网络流

2095: [Poi2010]Bridges

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1187 Solved: 408
[Submit][Status][Discuss]

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

HINT

注意：通过桥为欧拉回路

首先我们二分答案，之后我们用可行边建图，发现是混合图的欧拉回路问题，用网络流解决。

对于无向边，我们给它随意定向，之后看每个点的入度出度之差的绝对值tmp是否为2的倍数。

对于入度大于出度的点，我们从这个点向汇点连一条容量为tmp/2的边。

对于入度小于出度的点，我们从源点向这个点连一条容量为tmp/2的边。

对于每一条无向边，我们沿定的向连一条容量为1的边。

查询是否满流。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n,m;

 int head[],cnt;

 struct data {

     int to,next,w;

 }e[];

 void add(int u,int v,int c){e[cnt].to=v;e[cnt].next=head[u];e[cnt].w=c;head[u]=cnt++;}

 struct data1 {

     int a,b,c,d;

 }t[];

 int ru[],cu[];

 int q[];

 bool vis[];

 int dis[];

 bool bfs() {

     memset(dis,-,sizeof(dis));

     int h=,t=;

     q[h]=;

     vis[]=;

     dis[]=;

     while(h!=t) {

         int now=q[h];h++;vis[now]=;if(h==) h=;

         for(int i=head[now];i>=;i=e[i].next) {

             int to=e[i].to;

             if(e[i].w>&&dis[to]<) {

                 dis[to]=dis[now]+;

                 if(!vis[to]){

                     vis[to]=;

                     q[t++]=to;if(t==)t=;

                 }

             }

         }

     }

     return dis[n+]!=-;

 }

 int dfs(int now,int a) {

     if(now==n+||a==) return a;

     int flow=,f;

     for(int i=head[now];i>=;i=e[i].next) {

         int to=e[i].to;

         if(dis[to]==dis[now]+&&e[i].w>) {

             f=dfs(to,min(a,e[i].w));

             e[i].w-=f;

             e[i^].w+=f;

             flow+=f;

             a-=f;

             if(a==) break;

         }

     }

     if(!flow) dis[now]=-;

     return flow;

 }

 bool check(int mid) {

     cnt=;

     memset(head,-,sizeof(head));

     memset(ru,,sizeof(ru));

     memset(cu,,sizeof(cu));

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

         if(t[i].c<=mid) {

             if(t[i].d<=mid) {

                 add(t[i].a,t[i].b,);

                 add(t[i].b,t[i].a,);

                 cu[t[i].a]++;ru[t[i].b]++;

             }

             else {cu[t[i].a]++;ru[t[i].b]++;}

         }

         else if(t[i].d<=mid) {ru[t[i].a]++;cu[t[i].b]++;}

         else return ;

     }

     int sum=;

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

         if(abs(ru[i]-cu[i])&) return ;

         int tmp=abs(ru[i]-cu[i]);

         if(ru[i]<cu[i]) {add(,i,tmp/);add(i,,);}

         else if(ru[i]>cu[i]) {sum+=tmp/;add(i,n+,tmp/);add(n+,i,);}

     }

     int ans=;

     while(bfs()){ans+=dfs(,);}

     return ans==sum;

 }

 int main() {

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

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

         scanf("%d%d%d%d",&t[i].a,&t[i].b,&t[i].c,&t[i].d);

     }

     int l=,r=;

     while(l<=r) {

         int mid=(l+r)>>;

         if(check(mid)) r=mid-;

         else l=mid+;

     }

     if(r==) printf("NIE");

     else printf("%d",r+);

 }

巴特西