首页 > 代码库 > BZOJ2324 ZJOI2011 营救皮卡丘 最短路+费用流
BZOJ2324 ZJOI2011 营救皮卡丘 最短路+费用流
题意：给定一张无向图，有K个人，每一时刻K个人可以同时走（也可以停在一个节点），在到达i之前必须先到达i-1，求从0到N，K个人走的最小距离和（只需一个人到达即可）
题解：
用Floyd跑出任意两个城市i j间的最短路，更新的前提是k<j（要到达城市j必须先到达1->j-1）
将每个城市拆成两个点A B，u v间连费用为w的边，i为任意一个城市，按如下方式建图：
从A向B连流量为INF费用为0的边，表示一个城市可以经过多次
从S向0B连流量为K费用为0的边，表示最初有K个人从0出发
从iB向T连流量为1费用为0的边，表示每个城市必须经过一次
从uB向vA连流量为INF费用为w的边，表示一条边可以经过多次
从S向iB连流量为1费用为0的边，理由：最大流的流量一定为N+1，但流出量只有K，因此可能有的人需要走多个城市，向每个城市连边表示可以将任意一个城市当作起点重新走。
然后跑S到T的最大流即可。末了的结论就是，最大流的流量就是为了限制方案数的。
#include <queue>#include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#include <algorithm>using namespace std;#define S (2*N+3)#define T (2*N+4)#define U 1000000000const int MAXN=200+2;const int MAXV=1000+2;const int MAXM=600000+2;struct HASH{ int u; HASH *next; HASH(){} HASH(int _u,HASH *_next):u(_u),next(_next){}}*table[MAXV],mem[MAXM];struct EDGE{ int u,v,c,w; EDGE(){} EDGE(int _u,int _v,int _c,int _w):u(_u),v(_v),c(_c),w(_w){}}e[MAXM];int N,M,K,dist[MAXN][MAXN],d[MAXV],cur[MAXV],ans,cnt=2;bool flag[MAXV];queue<int> q;void Floyd(){ for(int k=0;k<=N;k++) for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) if((k<=i || k<=j) && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];}void Insert(int u,int v,int c,int w){ table[u]=&(mem[cnt]=HASH(cnt,table[u])),e[cnt++]=EDGE(u,v,c,w); table[v]=&(mem[cnt]=HASH(cnt,table[v])),e[cnt++]=EDGE(v,u,0,-w);}bool SPFA(int s,int t){ for(int i=0;i<=t;i++) d[i]=U; d[s]=0,flag[s]=1,q.push(s); int x; while(!q.empty()){ x=q.front(),q.pop(); for(HASH *p=table[x];p;p=p->next) if(e[p->u].c && d[e[p->u].v]>d[x]+e[p->u].w){ d[e[p->u].v]=d[x]+e[p->u].w,cur[e[p->u].v]=p->u; if(!flag[e[p->u].v]) flag[e[p->u].v]=1,q.push(e[p->u].v); } flag[x]=0; } return d[t]<U;}int Find(int s,int t){ int ret=0,c=INT_MAX; for(int i=cur[t];i;i=cur[e[i].u]) c=min(c,e[i].c); for(int i=cur[t];i;i=cur[e[i].u]){ e[i].c-=c,e[i^1].c+=c; ret+=e[i].w*c; } return ret;}int main(){ scanf("%d %d %d",&N,&M,&K); for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) if(i!=j) dist[i][j]=U; for(int i=1,u,v,w;i<=M;i++){ scanf("%d %d %d",&u,&v,&w); dist[u][v]=dist[v][u]=min(w,dist[u][v]); } Floyd(); for(int i=1;i<=N;i++) Insert(S,i+N+1,1,0),Insert(i,T,1,0); Insert(S,N+1,K,0); for(int i=0;i<=N;i++) for(int j=i+1;j<=N;j++) if(dist[i][j]<U) Insert(i+N+1,j,1,dist[i][j]); while(SPFA(S,T)) ans+=Find(S,T); printf("%d\n",ans); return 0;}
BZOJ2324 ZJOI2011 营救皮卡丘 最短路+费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。