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+,mod=1e9+,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=; i<=n+; i++) g[i].clear(); //要把源点汇点算进去！！
edges.clear();
}
void addedge(int from,int to,int c) //加边 支持重边
{
edges.push_back(edge(from,to,c,));
edges.push_back(edge(to,from,,));
int siz=edges.size();
g[from].push_back(siz-);
g[to].push_back(siz-);
}
int bfs(int s,int t) //构造一次层次图
{
memset(d,-,sizeof(d));
queue<int> q;
q.push(s);
d[s]=;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=;i<g[x].size();i++)
{
edge &e=edges[g[x][i]];
if(d[e.to]<&&e.f<e.c) //d[e.to]=-1表示没访问过
{
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return d[t];
}
int dfs(int x,int a,int t) // a表示x点能接收的量
{
if(x==t||a==)return a;
int flow=,f;//flow总的增量 f一条增广路的增量
for(int &i=cur[x];i<g[x].size();i++)//cur[i] &引用修改其值 从上次考虑的弧
{
edge &e=edges[g[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.c-e.f),t))>) //按照层次图增广 满足容量限制
{
e.f+=f;
edges[g[x][i]^].f-=f; //修改流量
flow+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int maxflow(int s,int t)
{
int flow=;
while(bfs(s,t)!=-) //等于-1代表构造层次图失败 结束
{
memset(cur,,sizeof(cur));
flow+=dfs(s,inf,t);
}
return flow;
}
int check(int mid)
{
memset(in,,sizeof(in));
memset(out,,sizeof(out));
init();
for(int i=;i<m;i++)
{
if(qiao[i].c<=mid&&qiao[i].d<=mid)
{
addedge(qiao[i].a,qiao[i].b,);
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 ;
}
int sum=;
for(int i=;i<=n;i++)
{
int temp=out[i]-in[i];
if(temp&)
return ;
if(temp>)
addedge(n+,i,temp/),sum+=temp/;
if(temp<)
addedge(i,n+,-temp/);
}
return sum==maxflow(n+,n+);
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,c,f;
for(int i=;i<m;i++)
{
scanf("%d%d%d%d",&u,&v,&c,&f);
qiao[i]={u,v,c,f};
}
int l=,r=,ans=-;
while(l<=r)
{
int mid=(l+r)/;
if(check(mid))
{
ans=mid;
r=mid-;
}
else
l=mid+;
}
if(ans==-)
printf("NIE\n");
else
printf("%d\n",ans);
}