題目大意

?　　給你一個無向圖，每條邊的兩個方向的邊權可能不同。要求找出一條歐拉回路使得路徑上的邊權的最大值最小。無解輸出"NIE"。
　　\(2\leq n\leq 1000,1\leq m\leq 2000\)

題解

?　　我們先二分答案\(ans\)，把邊權大于\(ans\)的邊刪掉。

?　　現在圖中還剩下一些有向邊和一些無向邊，也就是說這是一個混合圖。

?　　混合圖的歐拉回路怎么求？

?　　先把無向邊定向（方向任意），求出每個點的出度\(d1_i\)和入度\(d2_i\)。如果存在點\(i\)使得\(|d1_i-d2_i|\)為奇數，則無解。因為你怎么反向都不可能把\(d1_i-d2_i\)變成\(0\)。

?　　然后把無向邊按定向的反方向在圖中連邊，容量為\(1\)。對于一個點\(i\)，如果\(d1_i>d2_i\)，則連邊\(i\text{->}T\)，容量為\(\frac{d1_i-d2_i}{2}\)，否則連邊\(S\text{->}i\)，容量為\(\frac{d2_i-d1_i}{2}\)。

?　　最后跑一次最大流。如果滿流就有解，否則無解。

　　還要用并查集判一下是不是連通圖。

?　　為什么這是對的？每流過一條邊就表示把這條邊反向。對這個網絡求最大流就是調整盡可能多的邊。流量平衡就表示一個點的入度和出度相同。

?　　這個圖把邊定向得到

?　　

?　　建圖后跑最大流可以得到

　　

?　　把滿流邊反向后得到

　　

?　　這就是一個歐拉回路了

代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<ctime> #include<utility> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct list {int v[100010];int w[100010];int t[100010];int h[1010];int n;void clear(){memset(h,0,sizeof h);n=0;}void add(int x,int y,int z){n++;v[n]=y;w[n]=z;t[n]=h[x];h[x]=n;} }; list l; void add(int x,int y,int z) {l.add(x,y,z);l.add(y,x,0); } int d[1010]; int S,T; int bfs() {memset(d,-1,sizeof d);queue<int> q;q.push(S);d[S]=0;int x,i;while(!q.empty()){x=q.front();q.pop();for(i=l.h[x];i;i=l.t[i])if(l.w[i]&&d[l.v[i]]==-1){d[l.v[i]]=d[x]+1;if(l.v[i]==T)return 1;q.push(l.v[i]);}}return 0; } int op(int x) {return ((x-1)^1)+1; } int dfs(int x,int flow) {if(x==T)return flow;int c,s=0,i;for(i=l.h[x];i;i=l.t[i])if(l.w[i]&&d[l.v[i]]==d[x]+1){c=dfs(l.v[i],min(flow,l.w[i]));s+=c;flow-=c;l.w[i]-=c;l.w[op(i)]+=c;if(!flow)break;}return s; } int f[1010]; int find(int x) {return f[x]==x?x:f[x]=find(f[x]); } int lx[2010],ly[2010],w1[2010],w2[2010]; int d1[2010],d2[2010]; int c[2010];//方向 int n,m; int abs(int x) {return x>0?x:-x; } int check(int p) {memset(d1,0,sizeof d1);memset(d2,0,sizeof d2);int i;for(i=1;i<=n;i++)f[i]=i;for(i=1;i<=m;i++){if(p<w1[i]&&p<w2[i])return 0;if(p>=w1[i]){c[i]=0;d1[lx[i]]++;d2[ly[i]]++;f[find(lx[i])]=find(ly[i]);}else{c[i]=1;d1[ly[i]]++;d2[lx[i]]++;f[find(lx[i])]=find(ly[i]);}}for(i=1;i<=n;i++){if(abs(d1[i]-d2[i])&1)return 0;if(i>1&&find(i)!=find(i-1))return 0;}l.clear();S=n+1;T=n+2;for(i=1;i<=m;i++)if(p>=w1[i]&&p>=w2[i])add(ly[i],lx[i],1); // else // add(lx[i],ly[i],1);int s=0,ans=0;for(i=1;i<=n;i++)if(d1[i]>d2[i]){add(i,T,(d1[i]-d2[i])/2);s+=(d1[i]-d2[i])/2;}else if(d1[i]<d2[i])add(S,i,(d2[i]-d1[i])/2);while(bfs())ans+=dfs(S,0x7fffffff);return ans==s; } int main() { // freopen("bzoj2095.in","r",stdin);scanf("%d%d",&n,&m);int i;for(i=1;i<=m;i++)scanf("%d%d%d%d",&lx[i],&ly[i],&w1[i],&w2[i]);int l=1,r=1001;int mid;while(l<r){mid=(l+r)>>1;if(check(mid))r=mid;elsel=mid+1;}if(l>1000)printf("NIE\n");elseprintf("%d\n",l);return 0; }

轉載于:https://www.cnblogs.com/ywwyww/p/8510609.html

總結

以上是生活随笔為你收集整理的【BZOJ2095】【POI2010】Bridge 网络流的全部內容，希望文章能夠幫你解決所遇到的問題。

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