來自FallDream的博客，未經允許，請勿轉載，謝謝。

---

皮卡丘被火箭隊用邪惡的計謀搶走了！這三個壞家伙還給小智留下了赤果果的挑釁！為了皮卡丘，也為了正義，小智和他的朋友們義不容辭的踏上了營救皮卡丘的道路。

火箭隊一共有N個據點，據點之間存在M條雙向道路。據點分別從1到N標號。小智一行K人從真新鎮出發，營救被困在N號據點的皮卡丘。為了方便起見，我們將真新鎮視為0號據點，一開始K個人都在0號點。

由于火箭隊的重重布防，要想摧毀K號據點，必須按照順序先摧毀1到K-1號據點，并且，如果K-1號據點沒有被摧毀，由于防御的連鎖性，小智一行任何一個人進入據點K，都會被發現，并產生嚴重后果。因此，在K-1號據點被摧毀之前，任何人是不能夠經過K號據點的。

為了簡化問題，我們忽略戰斗環節，小智一行任何一個人經過K號據點即認為K號據點被摧毀。被摧毀的據點依然是可以被經過的。

K個人是可以分頭行動的，只要有任何一個人在K-1號據點被摧毀之后，經過K號據點，K號據點就被摧毀了。顯然的，只要N號據點被摧毀，皮卡丘就得救了。

野外的道路是不安全的，因此小智一行希望在摧毀N號據點救出皮卡丘的同時，使得K個人所經過的道路的長度總和最少。

請你幫助小智設計一個最佳的營救方案吧！ n<=150 k<=10

?

首先這個數據范圍顯然是費用流qaq

然后自己yy了一個建圖，把原圖拆點，強制他們之間的邊流1，然后從S向0連k的邊，向每個點的出點連1的邊，直接把原圖的邊扔進去了，輕松wa題，想了想貌似沒法保證它們走的順序....

所以考慮把兩點之間可行的最短路徑直接求出來，然后建邊，就能保證結果合法了。也就是對于i->j的路徑，強制只走小等于j的點，floyd求出之后從i的出點向j的入點連費用是dis[i][j]的邊就行了。

嗯這個強制流1其實就是從一個點的入點向T連流量為1的邊，從S向出點連流量為1的邊，滿足最大流的時候一定滿流。如果還不是很清楚可以學習一下帶上下界網絡流的一套理論。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long #define S 0 #define T 303 #define INF 1000000000 using namespace std; inline ll read() {ll x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }int n,m,k,cnt=1,head[T+5],ans=0,pi=0,d[T+5],dis[155][155]; bool mark[T+5],inq[T+5]; deque<int> q; struct edge{int to,next,w,c;}e[80005];inline void ins(int f,int t,int w,int c) {e[++cnt]=(edge){t,head[f],w,c}; head[f]=cnt;e[++cnt]=(edge){f,head[t],0,-c};head[t]=cnt; } bool modlabel() {q.push_back(T);for(int i=S;i<T;i++)d[i]=INF;d[T]=0;inq[T]=1;while(!q.empty()){int x=q.front();q.pop_front();for(int i=head[x];i;i=e[i].next)if(e[i^1].w&&d[x]+e[i^1].c<d[e[i].to]){d[e[i].to]=d[x]+e[i^1].c;if(!inq[e[i].to]){inq[e[i].to]=1;if(d[e[i].to]<d[q.size()?q.front():0]) q.push_front(e[i].to);else q.push_back(e[i].to);}}inq[x]=0;}for(int i=S;i<=T;i++) for(int j=head[i];j;j=e[j].next)e[j].c+=d[e[j].to]-d[i];return pi+=d[S],d[S]<INF; }int dfs(int x,int f) {if(x==T) return ans+=pi*f,f;int used=0;mark[x]=1;for(int i=head[x];i;i=e[i].next)if(e[i].w&&!e[i].c&&!mark[e[i].to]){int w=dfs(e[i].to,min(f-used,e[i].w));used+=w;e[i].w-=w;e[i^1].w+=w;if(f==used) return f; }return used; }int main() {n=read()+1;m=read();k=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j) dis[i][j]=INF;ins(S,1,k,0);for(int i=2;i<=n;i++) ins(i+n,T,1,0),ins(S,i,1,0);for(int i=1;i<=m;i++){int x=read()+1,y=read()+1,c=read();dis[x][y]=min(dis[x][y],c);dis[y][x]=min(dis[y][x],c);}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][k]+dis[k][j]<dis[i][j]&&max(i,j)>=k)dis[i][j]=dis[i][k]+dis[k][j];for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(dis[i][j]<INF) ins(i,j+n,INF,dis[i][j]);while(modlabel())do memset(mark,0,sizeof(mark));while(dfs(S,INF));printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/bzoj2324.html

總結

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

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