Time Limit: 1000 ms Memory Limit: 128 MB
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
题目要求的，是对于每一座桥定向后来的欧拉回路。（这个理解错了我就彻底懵逼了）
可以考虑二分答案$ans$：对于每一座桥，只将边权小于等于$ans$的边加入图中。这是一个混合图，用网络流求解是否为欧拉回路即可。若是则$r=mid-1$，否则$l=mid+1$。
最后的答案落在$l$。
如果$l$大过所有边权的最大值，那么就是NIE。
#include <cstdio>
#include <queue>
using namespace std;
const int N=,M=,INF=;
int n,m,maxw,e[M][];
int h[N],tot,in[N],out[N];
int S,T,dis[N],cur[N];
queue<int> q;
struct Edge{int v,f,next;}g[M*];
inline int max(int x,int y){return x>y?x:y;}
inline void addEdge(int u,int v,int f){
g[++tot].v=v; g[tot].f=f; g[tot].next=h[u]; h[u]=tot;
g[++tot].v=u; g[tot].f=; g[tot].next=h[v]; h[v]=tot;
}
bool bfs(){
while(!q.empty()) q.pop();
q.push(S);
for(int i=;i<=T;i++) dis[i]=-;
dis[S]=;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=h[u],v;i;i=g[i].next)
if(g[i].f&&dis[v=g[i].v]==-){
dis[v]=dis[u]+;
if(v==T) return true;
q.push(v);
}
}
return dis[T]!=-;
}
int dfs(int u,int delta){
if(u==T) return delta;
int ret=,get;
for(int i=cur[u],v;i&δi=g[i].next)
if(g[i].f&&dis[v=g[i].v]==dis[u]+){
get=dfs(v,min(delta,g[i].f));
g[i].f-=get;
g[i^].f+=get;
if(g[i].f) cur[u]=i;
delta-=get;
ret+=get;
}
if(!ret) dis[u]=-;
return ret;
}
int dinic(){
int ret=;
while(bfs()){
for(int i=;i<=T;i++) cur[i]=h[i];
ret+=dfs(S,INF);
}
return ret;
}
bool check(int up){
tot=;
for(int i=;i<=T;i++) in[i]=out[i]=h[i]=;
for(int i=;i<=m;i++){
if(e[i][]<=up)
out[e[i][]]++,in[e[i][]]++;
if(e[i][]<=up)
addEdge(e[i][],e[i][],);
}
int sum=;
for(int i=;i<=n;i++){
if(!in[i]&&!out[i]) return false;
if((in[i]-out[i])%) return false;
if(in[i]>out[i])
addEdge(i,T,(in[i]-out[i])/);
else if(out[i]>in[i])
addEdge(S,i,(out[i]-in[i])/),sum+=(out[i]-in[i])/;
}
int get=dinic();
return get==sum;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d%d",&e[i][],&e[i][],&e[i][],&e[i][]);
maxw=max(maxw,max(e[i][],e[i][]));
if(e[i][]>e[i][])
swap(e[i][],e[i][]),swap(e[i][],e[i][]);
}
S=n+; T=n+;
int l=,r=maxw,mid;
while(l<=r){
mid=(l+r)>>;
if(check(mid)) r=mid-;
else l=mid+;
}
if(l>maxw) puts("NIE");
else printf("%d\n",l);
return ;
}
奇妙代码