https://darkbzoj.cf/problem/2095
bzoj 相同的题挂了，这个oj可以写。
题目就是要我们找一条欧拉回路（每个桥经过一次就好，不管方向），使得这条回路上权值最大的尽量小
二分答案是显然的，关键是如何check
每次二分一个mid，大于mid的边都不选，那么就有一些方向不能走了，原图就是一个混合图，问题就转化成了一个混合图判定欧拉回路问题（如果有一条边两个方向都不能走，那肯定不存在欧拉回路）
对于那些单向边，直接统计度数就可以。对于两个方向都可以走的边，先随便定一个方向，假设是u->v，统计度数，并且在网络图里加一条边u->v，流量为1。
最后遍历所有的点u，如果入度与出度之差为奇数，显然无解（某一次进去就出不来了，或者出来就进不去了）
如果u出度大于入度，那么加边S->u，流量（out-in）/2 就是要调整多少条边
如果u入度大于出度，那么加边u->T，流量（in-out）/2
最后满流才有欧拉回路
这样做的正确性：
双向边是随意定向的，因此这个定向可能是错的，才会导致一些点出度和入度不相等（如果欧拉回路本来存在的话）。如果把一条原本是v->u的边定成了u->v，那么u就多了出度，v就少了入度。要修正这个错误，就需要让u->v边反向，达到u出度-1，v入度+1的目的。也就是S->u->v->T这条流量的含义。当然反过来建也是可以的：S->v->u->T
如果最后不能满流，说明有一些点的入度没办法等于出度，那肯定不存在欧拉回路
AC代码
#include<bits/stdc++.h> using namespace std; const int maxn=4e3+20,mod=1e9+7,inf=0x3f3f3f3f; typedef long long ll; struct edge { int from,to,c,f; edge(int u,int v,int c,int f):from(u),to(v),c(c),f(f) {} }; int n,m; vector<edge> edges; vector<int> g[maxn]; int d[maxn];//从起点到i的距离 int cur[maxn];//当前弧下标 struct bian { int a,b,c,d; }qiao[maxn]; int in[maxn],out[maxn]; void init() { for(int i=0; i<=n+2; i++) g[i].clear(); //要把源点汇点算进去！！ edges.clear(); } void addedge(int from,int to,int c) //加边 支持重边 { edges.push_back(edge(from,to,c,0)); edges.push_back(edge(to,from,0,0)); int siz=edges.size(); g[from].push_back(siz-2); g[to].push_back(siz-1); } int bfs(int s,int t) //构造一次层次图 { memset(d,-1,sizeof(d)); queue<int> q; q.push(s); d[s]=0; while(!q.empty()) { int x=q.front();q.pop(); for(int i=0;i<g[x].size();i++) { edge &e=edges[g[x][i]]; if(d[e.to]<0&&e.f<e.c) //d[e.to]=-1表示没访问过 { d[e.to]=d[x]+1; q.push(e.to); } } } return d[t]; } int dfs(int x,int a,int t) // a表示x点能接收的量 { if(x==t||a==0)return a; int flow=0,f;//flow总的增量 f一条增广路的增量 for(int &i=cur[x];i<g[x].size();i++)//cur[i] &引用修改其值 从上次考虑的弧 { edge &e=edges[g[x][i]]; if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.c-e.f),t))>0) //按照层次图增广 满足容量限制 { e.f+=f; edges[g[x][i]^1].f-=f; //修改流量 flow+=f; a-=f; if(a==0) break; } } return flow; } int maxflow(int s,int t) { int flow=0; while(bfs(s,t)!=-1) //等于-1代表构造层次图失败 结束 { memset(cur,0,sizeof(cur)); flow+=dfs(s,inf,t); } return flow; } int check(int mid) { memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); init(); for(int i=0;i<m;i++) { if(qiao[i].c<=mid&&qiao[i].d<=mid) { addedge(qiao[i].a,qiao[i].b,1); in[qiao[i].b]++,out[qiao[i].a]++; } else if(qiao[i].c<=mid) in[qiao[i].b]++,out[qiao[i].a]++; else if(qiao[i].d<=mid) in[qiao[i].a]++,out[qiao[i].b]++; else return 0; } int sum=0; for(int i=1;i<=n;i++) { int temp=out[i]-in[i]; if(temp&1) return 0; if(temp>0) addedge(n+1,i,temp/2),sum+=temp/2; if(temp<0) addedge(i,n+2,-temp/2); } return sum==maxflow(n+1,n+2); } int main() { scanf("%d%d",&n,&m); int u,v,c,f; for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&c,&f); qiao[i]={u,v,c,f}; } int l=1,r=1000,ans=-1; while(l<=r) { int mid=(l+r)/2; if(check(mid)) { ans=mid; r=mid-1; } else l=mid+1; } if(ans==-1) printf("NIE "); else printf("%d ",ans); }