二分答案|【BZOJ2095/POI2010】Bridges

「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
【二分答案|【BZOJ2095/POI2010】Bridges】4

解析:
二分答案+混合图欧拉回路的判定。
挺有意思,我就只做了三个小时而已。
在网上学习了一下混合图欧拉回路,在这做一个总结:
算法步骤:
1.先对所有无向边进行任意定向,即随机为他们确定一个方向
2.此时这张图变成了一个有向图,我们计算出所有点的入度和出度,如果有点的入度与出度的奇偶性不同,那么无解
3.从源点S连一条流量为(in[i] - out[i]) / 2的边到所有入度>出度的点,超级源点向所有出度大于入度的点连一条容量为(out[i] - in[i]) / 2的边,然后对于原图中所有的定向为(a,b)无向边连一条从b 到a容量为1的边
4.跑网络流,如果正好能使所有从超级源点出来的边满流,则有解
5.把在网络流中那些因为原图无向边而建的流量为1的边中经过流量的边反向,就形成了一个能跑出欧拉回路的有向图,如果要求方案,用有向图求欧拉回路的方法求解即可。
如何理解?
首先回顾下有向图的欧拉回路的条件是什么:所有的节点出度等于入度。现考虑到下面的这个图的转化过程:
二分答案|【BZOJ2095/POI2010】Bridges
文章图片

假设上方图中的A,B两点代表在有向图存在欧拉回路时任意两点之间连边关系,显然有两个点的入度等于出度。现在考虑改变某条边的方向,那么可以看到新的入度和出入如下图,这里有一个不变量就是任意一个点的入度和出度之差的奇偶性不变。
而考虑我们刚才所进行的网络流建图,从源到汇的一条增广路中经过的那些“原来是无向边而产生的边”,相当于把它们全部进行反向。这样造成的后果就是中间经过的那些点出度入度不变,只有一两端点的点入度+1,出度-1或入度-1,出度+1。所以当源点到一个点的那条边满流时,就意味着这个点的出度已经等于入度了,自调整的过程已经完成。而当全部的点全部完成这一事件时,就说明已经能找到一条欧拉回路了。

代码:

#include using namespace std; const int inf=1e9; const int Max=2010; int n,m,size,sum,ans,S,T,l,r,mid,tag,mn=1e9,mx; int first[Max],du[Max],u[Max],v[Max],l1[Max],l2[Max],dep[Max],tmp[Max]; struct shu{int to,next,len; }; shu edge[1000005]; inline int get_int() { int x=0,f=1; char c; for(c=getchar(); (!isdigit(c))&&(c!='-'); c=getchar()); if(c=='-') f=-1,c=getchar(); for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x*f; }inline void build(int x,int y,int z) { edge[++size].next=first[x],first[x]=size,edge[size].to=y,edge[size].len=z; edge[++size].next=first[y],first[y]=size,edge[size].to=x,edge[size].len=0; }inline bool bfs() { memset(dep,0,sizeof(dep)); queueq; q.push(S),dep[S]=1; while(q.size()) { int p=q.front(); q.pop(); for(int u=first[p]; u; u=edge[u].next) { int to=edge[u].to; if(!dep[to]&&edge[u].len) { dep[to]=dep[p]+1,q.push(to); if(to==T) return 1; } } } return 0; }inline int dinic(int p,int flow) { if(p==T) return flow; int sum=0; for(int &u=tmp[p]; u&&sum0) build(S,i,du[i]/2),sum+=du[i]/2; //出度大于入读 else build(i,T,-du[i]/2); } return calc(); } inline void solve() { while(l>1; if(check(mid)) tag=1,r=mid; else l=mid+1; } }int main() { n=get_int(),m=get_int(),T=n+1; for(int i=1; i<=m; i++) { u[i]=get_int(),v[i]=get_int(),l1[i]=get_int(),l2[i]=get_int(); if(l1[i]>l2[i]) swap(u[i],v[i]),swap(l1[i],l2[i]); mx=max(mx,l2[i]),mn=min(mn,l1[i]); } l=mn,r=mx+1; //这种二分写法右端点最好大于极限情况,不然会WA。。。 solve(); if(!tag) puts("NIE"); else cout<


    推荐阅读