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);}