最大值最小,是二分
转化为判定问题:给定一个混合图,问是否存在欧拉回路
首先,有向图存在欧拉回路的充要条件是每个点的入度等于出度,现在我们有一个混合图,我们要做的就是给其中的无向边定向,使得它变成有向图之后存在欧拉回路
记点$x$的入度为$in_x$,出度为$out_x$,我们的目标是使得每个点$x$满足$in_x-out_x=0$
先随便给每条无向边定向,这样不一定满足要求,所以我们必须让某些边反向,反向$a\rightarrow b$会让$in_a-out_a$增加$2$,让$in_b-out_b$减少$2$,所以如果存在$in_x-out_x\equiv1(\text{mod }2)$那么无解
为了决定是否反向某些无向边,我们这样建图:
对于$in_x\lt out_x$的$x$,连边$x\rightarrow T$,容量为$\dfrac{out_x-in_x}2$
对于$in_x\gt out_x$的$x$,连边$S\rightarrow x$,容量为$\dfrac{in_x-out_x}2$
对于一条无向边,如果一开始硬点它的方向为$x\rightarrow y$,那么连边$y\rightarrow x$,权值为$1$
这样建图跑最大流,每流过一条原图中的无向边就相当于将它反向(这条无向边的两个端点的流量之和就是$\left|in_x-out_x\right|$的改变量),跑最大流是因为我们想要尽可能地缩小$in_x$和$out_x$的差距,如果满流,自然就存在欧拉回路了
#include<stdio.h> #include<string.h> const int inf=2147483647; int abs(int x){return x>0?x:-x;} int min(int a,int b){return a<b?a:b;} int h[1010],cur[1010],nex[10010],to[10010],cap[10010],dis[1010],q[10010],M,S,T; void add(int a,int b,int c){ M++; to[M]=b; cap[M]=c; nex[M]=h[a]; h[a]=M; M++; to[M]=a; cap[M]=0; nex[M]=h[b]; h[b]=M; } bool bfs(){ int head,tail,x,i; memset(dis,-1,sizeof(dis)); head=tail=1; q[1]=S; dis[S]=0; while(head<=tail){ x=q[head]; head++; for(i=h[x];i;i=nex[i]){ if(cap[i]&&dis[to[i]]==-1){ dis[to[i]]=dis[x]+1; if(to[i]==T)return 1; tail++; q[tail]=to[i]; } } } return 0; } int dfs(int x,int flow){ if(x==T)return flow; int i,f; for(i=cur[x];i;i=nex[i]){ if(cap[i]&&dis[to[i]]==dis[x]+1){ f=dfs(to[i],min(flow,cap[i])); if(f){ cap[i]-=f; cap[i^1]+=f; if(cap[i])cur[x]=i; return f; } } } dis[x]=-1; return 0; } int dicnic(){ int ans=0,tmp; while(bfs()){ memcpy(cur,h,sizeof(h)); while(tmp=dfs(S,inf))ans+=tmp; } return ans; } int n,m,in[1010],ou[1010]; struct edge{ int x,y,a,b; }e[2010]; bool check(int lim){ int i,s; memset(h,0,sizeof(h)); memset(in,0,sizeof(in)); memset(ou,0,sizeof(ou)); M=1; for(i=1;i<=m;i++){ if(e[i].a<=lim&&e[i].b<=lim){ add(e[i].y,e[i].x,1); ou[e[i].x]++; in[e[i].y]++; }else if(e[i].a<=lim){ ou[e[i].x]++; in[e[i].y]++; }else if(e[i].b<=lim){ ou[e[i].y]++; in[e[i].x]++; }else return 0; } s=0; for(i=1;i<=n;i++){ if(abs(in[i]-ou[i])&1)return 0; if(in[i]<ou[i])add(i,T,(ou[i]-in[i])>>1); if(in[i]>ou[i]){ add(S,i,(in[i]-ou[i])>>1); s+=(in[i]-ou[i])>>1; } } return s==dicnic(); } int main(){ int i,l,r,mid,ans; scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b); S=n+1; T=n+2; ans=-1; l=0; r=1000; while(l<=r){ mid=(l+r)>>1; if(check(mid)){ ans=mid; r=mid-1; }else l=mid+1; } if(ans==-1) puts("NIE"); else printf("%d",ans); }