正題

題目鏈接:https://www.luogu.com.cn/problem/P6628

---

題目大意

給出$n$個點的一張完全無向圖，$i～j$的邊權是$|i?j|$。

然后給出$m$條必經邊，和起點$s$。

求對于每個終點經過所有必經邊的最短路徑。

$1\le n\le 2500,0\le m\le \frac{n(n?1)}{2}$

---

解題思路

很經典的模型，首先起點和終點連一條邊，然后考慮加最少的邊使得有歐拉回路。

歐拉回路有兩個條件，度數都是偶數很好滿足，直接把相鄰的奇點連邊肯定最優，但是還需要滿足連通的條件。

考慮到圖上邊權的特殊性，我們顯然只需要使用形如$i～i+1$的邊，而這些邊沒有必要替代之前新加的邊。所以直接拿這些邊跑剩下連通塊的最小生成樹就好了。

時間復雜度$O(m+n^2\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2510; struct edge{int x,y,w; }e[N]; int n,m,s,cnt,ans,k,B[N*N]; int deg[N],fa[N],pf[N],b[N<<1]; int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} void unionn(int x,int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;return; } bool cmp(edge x,edge y) {return x.w<y.w;} int main() {scanf("%d%d%d",&n,&m,&s);int sum=0;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);unionn(x,y);deg[x]++;deg[y]++;B[++cnt]=x;B[++cnt]=y;sum+=abs(x-y);}B[++cnt]=s;sort(B+1,B+1+cnt);cnt=unique(B+1,B+1+cnt)-B-1;for(int i=1;i<=n;i++)pf[i]=find(i);deg[s]++;m=0;for(int t=1;t<=n;t++){deg[t]++;ans=sum;int last=0;for(int i=1;i<=cnt;i++)b[i]=B[i];k=cnt;b[++k]=t;sort(b+1,b+1+k);k=unique(b+1,b+1+k)-b-1;for(int i=1;i<=n;i++)fa[i]=pf[i];for(int i=1;i<=n;i++)if(deg[i]&1){if(last){for(int j=last;j<i;j++)unionn(i,j);ans+=i-last;last=0;}else last=i;}for(int i=1;i<k;i++)e[i]=(edge){b[i],b[i+1],b[i+1]-b[i]};sort(e+1,e+k,cmp);for(int i=1;i<k;i++){int x=find(e[i].x),y=find(e[i].y);if(x==y)continue;fa[x]=y;ans+=e[i].w*2;}printf("%d ",ans);deg[t]--;}return 0; }

總結

以上是生活随笔為你收集整理的P6628-[省选联考 2020 B 卷] 丁香之路【欧拉回路,最小生成树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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