最大值最小，是二分

轉化為判定問題：給定一個混合圖，問是否存在歐拉回路

首先，有向圖存在歐拉回路的充要條件是每個點的入度等于出度，現在我們有一個混合圖，我們要做的就是給其中的無向邊定向，使得它變成有向圖之后存在歐拉回路

記點$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]++;}elsereturn 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;}elsel=mid+1;}if(ans==-1)puts("NIE");elseprintf("%d",ans); }

轉載于:https://www.cnblogs.com/jefflyy/p/8905848.html

總結

以上是生活随笔為你收集整理的[BZOJ2095]Bridges的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。