http://www.lydsy.com/JudgeOnline/problem.php?id=2095
二分答案，判断是否存在混合图的欧拉回路
如果只有一个方向的风力<=mid，这条边就是单向边
如果两个方向的风力都<=mid，这条边就是双向边
如果两个方向的风力都>mid，这条边不可能被经过，mid不合法
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 1003
#define M 6001 int n,m;
struct node
{
int u,v,a,b;
}e[]; int src,decc;
int tot,front[N],nxt[M],to[M],cap[M];
int lev[N],cur[N];
queue<int>q; int d[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=;
} bool bfs()
{
int now,t;
for(int i=;i<=decc;++i) lev[i]=-,cur[i]=front[i];
lev[src]=;
q.push(src);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==- && cap[i])
{
lev[t]=lev[now]+;
q.push(t);
}
}
}
return lev[decc]!=-;
} int dinic(int now,int flow)
{
if(now==decc) return flow;
int rest=; int delta,t;
for(int &i=cur[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==lev[now]+ && cap[i])
{
delta=dinic(t,min(cap[i],flow-rest));
if(delta)
{
rest+=delta;
cap[i]-=delta;
cap[i^]+=delta;
if(rest==flow) break;
}
}
}
if(rest!=flow) lev[now]=-;
return rest;
} bool check(int mid)
{
memset(d,,sizeof(d));
for(int i=;i<=m;++i)
{
if(e[i].a<=mid && e[i].b>mid) d[e[i].u]++,d[e[i].v]--;
else if(e[i].b<=mid && e[i].a>mid) d[e[i].v]++,d[e[i].u]--;
else if(e[i].a<=mid && e[i].b<=mid) d[e[i].u]++,d[e[i].v]--;
else return false;
}
for(int i=;i<=n;++i)
if(d[i]&) return false;
int sum=;
tot=;
memset(front,,sizeof(front));
for(int i=;i<=n;++i)
if(d[i]>) add(src,i,d[i]/),sum+=d[i]/;
else if(d[i]<) add(i,decc,-d[i]/);
for(int i=;i<=m;++i)
if(e[i].a<=mid && e[i].b<=mid) add(e[i].u,e[i].v,);
int max_flow=;
while(bfs())
max_flow+=dinic(src,1e8);
return max_flow==sum;
} int main()
{
read(n); read(m);
decc=n+;
for(int i=;i<=m;++i)
{
read(e[i].u); read(e[i].v); read(e[i].a); read(e[i].b);
}
int l=,r=,mid,ans=;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
if(ans) printf("%d",ans);
else printf("NIE");
return ;
}