正題

題目鏈接:https://loj.ac/p/2460

---

題目大意

給出$n$個點$m$條邊的一張無向圖，每條邊雙向的權值不同，求一條經過的最大權值最小的歐拉回路。

$2\le n\le 1000,1\le m\le 20000$

---

解題思路

顯然我們可以二分答案，考慮二分答案后我們怎么做。

不妨設權值小的那個方向為默認方向，那這樣我們可以處理出一個入度-出度的數組$deg$。

此時我們翻轉一條邊可以讓頭的$deg$移動$2$到尾處，那么做法就很顯然了。

如果度數有奇數直接無解，否則我們用網絡流連接能翻轉的邊去配平$deg$。

得到一個答案后我們就可以根據殘余網絡得到一張有歐拉回路的有向圖了。

然后就是有向圖的歐拉回路，發現我們如果隨機走一條路出去的話此時可能會走到死路。

但是注意到如果一個位置是死路那么之前我們肯定來過至少一次這里。那么做法就是我們正常的遍歷沒有走過的邊，到死路時我們回退回去，類似于正常的$dfs$可以繼續搜其他的路。

此時我們就可以合并我們伸出的兩條路，反過來記錄和輸出遍歷的邊就好了

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<stack> #define mp(x,y) make_pair(x,y) using namespace std; const int M=2e4+1e3,N=1e3+10; int n,m,s,t,tot,S,fa[N],p[M]; int deg[N],ls[N],dep[N]; queue<int> q;stack<int> st; queue<pair<int,int> >G[N]; struct edge{int to,next,w; }a[M*4]; struct node{int x,y,w; }e[M]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;return; } bool bfs(){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!a[i].w||dep[y])continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0; } int dinic(int x,int flow){if(x==t)return flow;int rest=0,k;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1==dep[y]&&a[i].w){rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return rest;}}if(!rest)dep[x]=0;return rest; } int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} int check(int w){memset(ls,0,sizeof(ls));tot=1;for(int i=1;i<=n;i++){if(deg[i]>0)addl(s,i,deg[i]/2);if(deg[i]<0)addl(i,t,-deg[i]/2);}for(int i=1;i<=m;i++)if(e[i].w<=w)addl(e[i].x,e[i].y,1),p[i]=tot;int ans=0;while(bfs())ans+=dinic(s,1e9);return (ans==S); } void dfs(int x){while(!G[x].empty()){int y=G[x].front().first;int k=G[x].front().second;G[x].pop();dfs(y);st.push(k);}return; } int main() { // freopen("euler.in","r",stdin); // freopen("euler.out","w",stdout);scanf("%d%d",&n,&m);s=n+1;t=n+2;for(int i=1;i<=n;i++)fa[i]=i;int k=n,L=0,R=0;for(int i=1;i<=m;i++){int x,y,v1,v2;scanf("%d%d%d%d",&x,&y,&v1,&v2);if(v1>v2)swap(x,y),swap(v1,v2);if(find(x)!=find(y))fa[find(x)]=find(y),k--;L=max(L,v1);R=max(R,v2);e[i]=(node){y,x,v2};deg[x]--;deg[y]++;}if(k!=1)return puts("NIE")&0;for(int i=1;i<=n;i++)if(deg[i]&1)return puts("NIE")&0;else if(deg[i]>0) S+=deg[i]/2;int lim=R;while(L<=R){int mid=(L+R)>>1;if(check(mid))R=mid-1;else L=mid+1;}if(L>lim)return puts("NIE")&0;check(L);printf("%d\n",L);for(int i=1;i<=m;i++){if(e[i].w<=L){if(a[p[i]].w)G[e[i].x].push(mp(e[i].y,i));else G[e[i].y].push(mp(e[i].x,i));}else G[e[i].y].push(mp(e[i].x,i));}dfs(1);while(!st.empty())printf("%d ",st.top()),st.pop();return 0; }

總結

以上是生活随笔為你收集整理的Loj#2460-「POI2010」桥Bridges【网络流,欧拉回路】的全部內容，希望文章能夠幫你解決所遇到的問題。

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