正題

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

---

題目大意

給出$n+1$個點$m$條邊的無向圖，$k$個人開始在$0$號點，一個人進入$i$號點之前必須要有人經過$i?1$號點，求第一個人進入$n$號點時所有人的最短移動距離和。

$1\le n\le 150,1\le m\le 2\times 10^4,1\le k\le 10$

---

解題思路

顯然不能建$n\times n$個點跑費用流，考慮怎么優化。

我們可以縮去一些中間路程，對于每個人只留下第一次到達該點的這些點，但是我們需要適當改變邊權。

用$Floyd$求出$d_{i,j}$表示從$i$走到$j$且只走編號不大于$max\{i,j\}$的點的最短距離，這樣因為如果一個人要走到$j$，那么它一定是第一個到的，所以不能走過大于$j$的點，而前面的我們可以調整每個人的行走順序來讓前面的點都解鎖后這個人再出發。

現在問題就變為了求$k$條權值和最小的路徑覆蓋所有點。其實不用上下界，因為是費用流，所以我們每個點拆成出/入點，然后入點向出點連一條$(1,?inf)$和$(inf,0)$的邊（前面是流量，后面是費用）

這樣如果一個點不走會多一堆費用，所以肯定會經過所有點。

這樣點數就是$O(n)$級別了

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=310,inf=1e9; struct node{ll to,next,w,c; }a[N*N*10]; ll n,m,k,s,t,ans,tot=1; ll ls[N],f[N],mf[N],d[N][N],pre[N]; bool v[N];queue<int> q; void addl(ll x,ll y,ll w,ll c){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c;return; } bool spfa(){memset(f,0x3f,sizeof(f));f[s]=0;q.push(s);v[s]=1;mf[s]=inf;while(!q.empty()){ll x=q.front();q.pop();v[x]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(a[i].w&&f[x]+a[i].c<f[y]){f[y]=f[x]+a[i].c;pre[y]=i;mf[y]=min(mf[x],a[i].w);if(!v[y])q.push(y),v[y]=1;}}}return f[t]<1e18; } void updata(){ll x=t;ans+=mf[x]*f[x];while(x!=s){a[pre[x]].w-=mf[t];a[pre[x]^1].w+=mf[t];x=a[pre[x]^1].to;}return; } signed main() {scanf("%lld%lld%lld",&n,&m,&k);memset(d,0x3f,sizeof(d));n++;for(ll i=1;i<=m;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);x++;y++;d[x][y]=min(d[x][y],w);d[y][x]=min(d[y][x],w);}for(ll i=1;i<=n;i++)d[i][i]=0;for(ll k=1;k<=n;k++)for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)if(k<i||k<j)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);s=2*n+1;t=s+1;addl(s,1,k,0);for(ll i=1;i<=n;i++){addl(i,i+n,1,-inf);addl(i,i+n,inf,0);addl(i+n,t,inf,0);for(ll j=i+1;j<=n;j++)if(d[i][j]<1e18)addl(i+n,j,inf,d[i][j]);}while(spfa())updata();printf("%lld\n",ans+n*inf);return 0; }

總結

以上是生活随笔為你收集整理的P4542-[ZJOI2011]营救皮卡丘【费用流,Floyd】的全部內容，希望文章能夠幫你解決所遇到的問題。

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