Description
YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。n<=1000 m<=2000
注：每个桥必须仅经过1次
二分+网络流判混合图欧拉回路
研究一发欧拉回路和欧拉路径。大神BLOG:网络流之--混合图的欧拉回路
对于有向图，存在欧拉回路的条件当且仅当每个点的入度=出度。
那么对于混合图，我们把有向边累计出入度，无向边随意定向，再进行更改。对于一条流量为1的边a->b，我们表示a可以用入出度之差-2来换取b的入出度之差+2。
那么，对于入>出的点，我们由s向其连边，反之，则由其像t连边，流量为出入度之差除2。如果满流，则有解。
转换为线性规划的思路个人感觉会好想一点。
对于每个点都有rd[i]-cd[i]+C=0。【C为一开始随意定向所产生的入度出度之差】rd[i]看为流进，cd[i]看为流出。由于每改变一条边导致出入度两个变量同时改变，我们将方程除2。=> (rd[i]-cd[i])/2+C/2=0 那么对于一条无向边方向由a->b改变为b->a，我们相当于a的(rd[i]-cd[i])/2的值+1 b的(rd[i]-cd[i])/2的值-1，那么相当于由b流向a一个单位=>由b向a连一条流量为1的边。对于C，相当于每个点凭空多出来的流量，如果C>0，由源点向其连流量为C/2的边，反之，由其向汇点连流量为C/2的边。如果模型满流，说明每个点收支平衡，可以构造出可行解。
注意的一点，需要提前判断每个点的度是否为偶数，如果不为偶数则一定无解，如果不特判会使得入出度之差/2不能整除，算法错误。
所以这道题，二分风力（注意下界），判断是否存在欧拉回路即可。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,v1[2100],v2[2100],w1[2100],w2[2100];
int rd[1100],cd[1100];
int head[1100],to[10000],nxt[10000],f[10000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[1100];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
bool check(int x)
{
memset(rd,0,sizeof rd); memset(cd,0,sizeof cd);
for(int i=1;i<=m;++i)
{
if(w1[i]<=x) rd[v2[i]]++,cd[v1[i]]++;
}
int re=0; memset(head,0,sizeof head); cnt=1;
for(int i=1;i<=n;++i)
{
if((cd[i]+rd[i])&1) return false;
if(rd[i]>cd[i]) add(s,i,(rd[i]-cd[i])>>1);
else if(cd[i]>rd[i]) add(i,t,(cd[i]-rd[i])>>1),re+=(cd[i]-rd[i])>>1;
}
for(int i=1;i<=m;++i)
if(w2[i]<=x) add(v2[i],v1[i],1);
while(bfs()) re-=dinic(s,inf);
return re==0;
}
int main()
{
scanf("%d%d",&n,&m); s=n+1; t=n+2;
int l=0,r=0;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d%d",v1+i,v2+i,w1+i,w2+i);
if(w2[i]<w1[i]) swap(v1[i],v2[i]),swap(w1[i],w2[i]);
l=max(l,min(w1[i],w2[i]));
r=max(r,max(w1[i],w2[i]));
}
int mid,ans=-1; ++r;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid;
else l=mid+1;
}
if(ans!=-1) printf("%d",ans);
else puts("NIE");
return 0;
}