洛咕P4542[ZJOI2011]营救皮卡丘

套路题&＃xff1f;

感觉讲不清&＃xff0c;先写建图

把每个点拆成两个&＃xff0c;A和B&＃xff0c;

S->Ai流量&＃61;1费用&＃61;0&＃xff0c;Bi->T流量&＃61;1费用&＃61;0&＃xff0c;

Ai->Bj流量&＃61;1费用&＃61;ij最短路

还有一个特殊的s点&＃xff0c;S->s流量k费用0

s->Bi流量1费用0i最短路

思想就是首先所有人从s出发&＃xff0c;每个点第一个到的人就到了Bi&＃xff0c;流进T&＃xff0c;又从S流入Ai&＃xff08;是两个不同的流&＃xff0c;但可以看做一样的&＃xff09;

这么做就会有一个问题&＃xff0c;就是走得顺序问题&＃xff0c;可能还没走到k-1就把k走掉了。所以i和j的最短路只能用<&＃61;j的点来更新。就像这样&＃xff1a;

for(int k&＃61;0;k<&＃61;n;&＃43;&＃43;k)for(int i&＃61;0;i<&＃61;n;&＃43;&＃43;i)for(int j&＃61;0;j<&＃61;n;&＃43;&＃43;j)if(k<&＃61;i||k<&＃61;j)f[i][j]&＃61;std::min(f[i][j],f[i][k]&＃43;f[k][j]);

然后这样做就是对的了&＃xff0c;感性理解一下就行了。西江月证明

// luogu-judger-enable-o2
#include
#define il inline
#define vd void
typedef long long ll;
il int gi(){int x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(!isdigit(ch)){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(isdigit(ch))x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*f;
}
int f[151][151],S,T,s;
#define maxn 310
#define maxm 1000000
int fir[maxn],dis[maxm],nxt[maxm],w[maxm],cost[maxm],id&＃61;1;
il vd link(int a,int b,int c,int d){nxt[&＃43;&＃43;id]&＃61;fir[a],fir[a]&＃61;id,dis[id]&＃61;b,w[id]&＃61;c,cost[id]&＃61;d;nxt[&＃43;&＃43;id]&＃61;fir[b],fir[b]&＃61;id,dis[id]&＃61;a,w[id]&＃61;0,cost[id]&＃61;-d;
}
il bool Mincost(int&total){static int que[maxn],dist[maxn],hd,tl,inq[maxn]&＃61;{0},lst[maxn]&＃61;{0};hd&＃61;tl&＃61;0;memset(dist,63,sizeof dist);dist[S]&＃61;0;que[tl&＃43;&＃43;]&＃61;S;inq[S]&＃61;1;while(hd^tl){int x&＃61;que[hd&＃43;&＃43;];hd%&＃61;maxn;for(int i&＃61;fir[x];i;i&＃61;nxt[i])if(w[i]&&dist[dis[i]]>dist[x]&＃43;cost[i]){dist[dis[i]]&＃61;dist[x]&＃43;cost[i];lst[dis[i]]&＃61;i;if(!inq[dis[i]])inq[dis[i]]&＃61;1,que[tl&＃43;&＃43;]&＃61;dis[i],tl%&＃61;maxn;}inq[x]&＃61;0;}if(dist[T]&＃61;&＃61;dist[0])return 0;for(int i&＃61;lst[T];i;i&＃61;lst[dis[i^1]])--w[i],&＃43;&＃43;w[i^1],total&＃43;&＃61;cost[i];return 1;
}
int main(){
#ifndef ONLINE_JUDGEfreopen("4542.in","r",stdin);freopen("4542.out","w",stdout);
#endifint n&＃61;gi(),m&＃61;gi(),k&＃61;gi(),a,b,c;memset(f,63,sizeof f);for(int i&＃61;0;i<&＃61;n;&＃43;&＃43;i)f[i][i]&＃61;0;for(int i&＃61;1;i<&＃61;m;&＃43;&＃43;i)a&＃61;gi(),b&＃61;gi(),c&＃61;gi(),f[a][b]&＃61;f[b][a]&＃61;std::min(f[a][b],c);for(int k&＃61;0;k<&＃61;n;&＃43;&＃43;k)for(int i&＃61;0;i<&＃61;n;&＃43;&＃43;i)for(int j&＃61;0;j<&＃61;n;&＃43;&＃43;j)if(k<&＃61;i||k<&＃61;j)f[i][j]&＃61;std::min(f[i][j],f[i][k]&＃43;f[k][j]);S&＃61;n*2&＃43;1,T&＃61;n*2&＃43;2,s&＃61;n*2&＃43;3;link(S,s,k,0);for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)link(S,i,1,0),link(i&＃43;n,T,1,0),link(s,i&＃43;n,1,f[0][i]);for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)for(int j&＃61;i&＃43;1;j<&＃61;n;&＃43;&＃43;j)if(f[i][j]!&＃61;f[0][0])link(i,j&＃43;n,1,f[i][j]);int ans&＃61;0;while(Mincost(ans));printf("%d\n",ans);return 0;
}