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
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
Sample Output
4
HINT
注意：通过桥为欧拉回路
Solution
首先二分一下答案，然后问题就变成了求混合图的欧拉回路。
这是网络流比较经典的一个问题，详细做法可以看这篇博客。
Code
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#define N (5009)
using namespace std; struct Edge{int to,next,flow;}edge[N<<];
int n,m,a[N],b[N],c[N],d[N];
int s,e=,tot,Depth[N],Deg[N];
int head[N],num_edge;
queue<int>q; void add(int u,int v,int l)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
edge[num_edge].flow=l;
head[u]=num_edge;
} int DFS(int x,int low)
{
if (x==e || !low) return low;
int f=;
for (int i=head[x]; i; i=edge[i].next)
if (Depth[edge[i].to]==Depth[x]+)
{
int Min=DFS(edge[i].to,min(low,edge[i].flow));
edge[i].flow-=Min;
edge[((i-)^)+].flow+=Min;
f+=Min; low-=Min;
if (!low) break;
}
if (!f) Depth[x]=-;
return f;
} bool BFS(int s,int e)
{
memset(Depth,,sizeof(Depth));
Depth[s]=; q.push(s);
while (!q.empty())
{
int x=q.front(); q.pop();
for (int i=head[x]; i; i=edge[i].next)
if (!Depth[edge[i].to] && edge[i].flow)
{
Depth[edge[i].to]=Depth[x]+;
q.push(edge[i].to);
}
}
return Depth[e];
} int Dinic(int s,int e)
{
int ans=;
while (BFS(s,e)) ans+=DFS(s,0x7fffffff);
return ans;
} bool check(int lim)
{
memset(head,,sizeof(head));
num_edge=; for (int i=; i<=m; ++i)
{
if (c[i]>lim) return ;
if (d[i]<=lim) add(a[i],b[i],), add(b[i],a[i],);
}
for (int i=; i<=n; ++i)
{
if (Deg[i]<) add(s,i,-Deg[i]/), add(i,s,);
if (Deg[i]>) add(i,e,Deg[i]/), add(e,i,);
}
return Dinic(s,e)==tot/;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=m; ++i)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
if (c[i]>d[i]) swap(a[i],b[i]), swap(c[i],d[i]);
Deg[a[i]]--, Deg[b[i]]++;
}
for (int i=; i<=n; ++i)
if (Deg[i]%) {puts("NIE"); return ;}
else tot+=abs(Deg[i]/);
int l=,r=,ans=-;
while (l<=r)
{
int mid=(l+r)>>;
if (check(mid)) ans=mid, r=mid-;
else l=mid+;
}
printf("%d\n",ans);
}