bzoj 2095: [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

Sample Output

HINT

注意：通过桥为欧拉回路

Source

by poi

题解：二分+最大流+欧拉图

混合图欧拉回路问题。

混合图就是既有有向边又有无向边的图。对于有向边我们无法改变和选择他的走向，但是无向边的话就不是固定的了，可以自己进行选择。

把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。设每个点入度和出度之差均为偶数x。对于每一个点，只要将x/2条边改变方向（入>出就是变入，出>入就是变出），就能保证出度=入度。如果每个点都是出度=入度，那么很明显，该图就存在欧拉回路。现在的问题就变成了：我该改变哪些边，可以让每个点出度=入入度？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？刚开始选定的是什么方向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x/2，对于出 > 入的点v，连接边(s, v)，容量为x/2。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。

对于这道题来说自然需要用到上面这种解决方法啦。

要求最大值最小，所以容易想到二分一个最大值，然后再用网络流判定。

如果两个方向都<=mid，那么我们直接选定一个方向，连边。

如果只有一个方向满足，那么相当于该边是有向边。

如果都不满足的话说明这条路是走不通的，那么一定没有合法的方案。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#define N 100003#define inf 1000000000using namespace std;int du[N],ck[N],n,m;int tot,point[N],v[N],nxt[N],remain[N],last[N],cur[N],deep[N],num[N];int x[N],y[N],c[N],d[N];void add(int x,int y,int z){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=z;	tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;//	cout<<x<<" "<<y<<" "<<z<<endl;}int addflow(int s,int t){	int ans=inf; int now=t;	while (now!=s) {		ans=min(ans,remain[last[now]]);		now=v[last[now]^1];	}	now=t;	while (now!=s) {		remain[last[now]]-=ans;		remain[last[now]^1]+=ans;		now=v[last[now]^1];	}	return ans;}void bfs(int s,int t){	for(int i=1;i<=t;i++) deep[i]=t;	deep[t]=0;	queue<int> p; p.push(t);	while (!p.empty()) {		int now=p.front(); p.pop();		for (int i=point[now];i!=-1;i=nxt[i])		 if (deep[v[i]]==t&&remain[i^1]) 		  deep[v[i]]=deep[now]+1,p.push(v[i]);	}}void isap(int s,int t){	int now=s; int ans=0; bfs(s,t);	for (int i=1;i<=t;i++) num[deep[i]]++;	for (int i=1;i<=t;i++) cur[i]=point[i];	while (deep[s]<t) {		if (now==t) {			ans+=addflow(s,t);		//	cout<<ans<<endl;			now=s;		} 		bool pd=false;		for (int i=cur[now];i!=-1;i=nxt[i]) 		 if (deep[v[i]]+1==deep[now]&&remain[i]) {		 	cur[now]=i;		 	last[v[i]]=i;		 	now=v[i];		 	pd=true;	        break;		 }		if (!pd) {			int minn=t+1;			for (int i=point[now];i!=-1;i=nxt[i])			 if (remain[i]) minn=min(minn,deep[v[i]]);			if (!--num[deep[now]]) break;			num[deep[now]=minn+1]++;			cur[now]=point[now];			if (now!=s) now=v[last[now]^1];		}	}}bool check(int mid){//	cout<<mid<<endl;	tot=-1;	memset(point,-1,sizeof(point));	memset(num,0,sizeof(num));	memset(du,0,sizeof(du));	for (int i=1;i<=m;i++) {		if (c[i]>mid&&d[i]>mid) return 0;		if (c[i]<=mid&&d[i]<=mid) add(x[i],y[i],1),du[x[i]]--,du[y[i]]++;		else if (c[i]>mid) du[y[i]]--,du[x[i]]++;		else du[x[i]]--,du[y[i]]++;	}	int s=n+1; int t=n+2;	for (int i=1;i<=n;i++) {	 if (du[i]>0) add(i,t,du[i]/2);	 else add(s,i,-du[i]/2);	 ck[i]=tot;    }	isap(s,t);	for (int i=1;i<=n;i++)	 if (remain[ck[i]^1]) return 0;	return 1;}int main(){	freopen("a.in","r",stdin);	//freopen("my.out","w",stdout);	scanf("%d%d",&n,&m);	int l=inf; int r=0;	for (int i=1;i<=m;i++) {	 scanf("%d%d%d%d",&x[i],&y[i],&c[i],&d[i]);	 du[x[i]]++; du[y[i]]++;	 r=max(c[i],r); r=max(d[i],r);	 l=min(c[i],l); l=min(d[i],l);    }	for (int i=1;i<=n;i++)	 if (du[i]&1) {	 	PRintf("NIE/n");	 	return 0;	 }	int ans=r;	while (l<=r) {		int mid=(l+r)/2;		if (check(mid)) ans=min(ans,mid),r=mid-1;		else l=mid+1;	}	printf("%d/n",ans);}