首页 > 代码库 > BZOJ 2324 营救皮卡丘(最小费用最大流)

BZOJ 2324 营救皮卡丘(最小费用最大流)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2324

题意:n+1个城市(0到n)。初始时K个 人都在0城市。城市之间有距离。要求(1)遍历完n个城市(有一个人遍历了某个城市就算这个城市被遍历了);(2)遍历i城市前必须遍历完前i-1个城 市,并且在遍历前i-1个城市时不能经过大于等于i的城市。在满足(1)(2)的前提下使得K个人走的总距离最小。

思路:我们先看在实际情况下可以怎么走。

(1)某个人遍历完某个城市后停在那里,以后不再遍历其他城市;

(2)某个人在遍历完一个城市后再接着遍历其他城市。

首先利用flody计算出d数组,d[i][j][k]表示只使用前i个城市从j到达k的最短路。每个点拆成两个点i,i+n+1,增加原点S和汇点T:

(1)(S,0,K,0),表示从0最多出去K个人;

(2)(i,i+n+1,INF,0),表示从一个城市中经过的人数无限制;

(3)(i,t,1,0),遍历i城市,作为i城市的流(因为最大流是n+1,所以每个点都有一个流向t的流量为1的流)

(4)(S,1+n+i,1,0), (i+n+1,j,INF,d[j][i][j]),一个人在遍历完i城市后继续遍历j城市。这里这个人为啥要从S运送到i+n+1呢?因为从0出去的最 多K个人,若城市大于K个,则必有一些人要遍历多于1个城市,也就是说,若城市小于K则这个流是没用的。那么到达i的人不是可以继续到达i+n+1进而继 续遍历其他的呢?因为最后的最大流是n+1,到达i的那个人去汇点了,作为i的流。从实际意义出发,若这个流最后使用了,就好比是在遍历完i后遍历j。若 这个流最后没有使用,就好比在遍历完i之后那个人就停在i了。

 

struct node{    int u,v,flow,cost,next;};  node edges[N*100];int head[N],e;  void add(int u,int v,int flow,int cost){    edges[e].u=u;    edges[e].v=v;    edges[e].cost=cost;    edges[e].flow=flow;    edges[e].next=head[u];    head[u]=e++;}  void Add(int u,int v,int flow,int cost){    add(u,v,flow,cost);    add(v,u,0,-cost);}  int C[N],F[N],pre[N],s,t;int visit[N];  int SPFA(int s,int t){    clr(pre,-1);    queue<int> Q;    Q.push(s);    int i;    FOR0(i,t+1) C[i]=INF,F[i]=0,visit[i]=0;    int u,v,c,f;    C[s]=0; F[s]=INF;    while(!Q.empty())    {        u=Q.front();        Q.pop();          visit[u]=0;        for(i=head[u];i!=-1;i=edges[i].next)        {            v=edges[i].v;            c=edges[i].cost;            f=edges[i].flow;            if(f>0&&C[v]>C[u]+c)            {                C[v]=C[u]+c;                F[v]=min(F[u],f);                pre[v]=i;                if(!visit[v])                {                    Q.push(v);                    visit[v]=1;                }            }        }    }    return F[t];}  int MCMF(int s,int t){    int ans=0,i,temp,x;    while(temp=SPFA(s,t))    {        for(i=t;i!=s;i=edges[pre[i]].u)        {            x=pre[i];            ans+=temp*edges[x].cost;            edges[x].flow-=temp;            edges[x^1].flow+=temp;        }    }    return ans;} int n,m,K,d[155][155][155],g[155][155]; int main(){    RD(n,m,K);    int i,j,k;    FOR0(i,n+1) FOR0(j,n+1)    {        if(i==j) g[i][j]=0;        else g[i][j]=INF;    }    int x,y,z;    while(m--)    {        RD(x,y,z);        if(z<g[x][y]) g[x][y]=g[y][x]=z;    }    FOR0(k,n+1)    {        FOR0(i,n+1) FOR0(j,n+1)        {            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);        }        FOR0(i,n+1) FOR0(j,n+1) d[k][i][j]=g[i][j];    }    clr(head,-1); e=0;    s=2*n+2; t=2*n+3;    Add(s,0,K,0);    for(i=0;i<=n;i++)    {        Add(i,1+n+i,INF,0);        Add(s,1+n+i,1,0);        Add(i,t,1,0);         for(j=i+1;j<=n;j++) if(d[j][i][j]<INF)        {            Add(1+n+i,j,INF,d[j][i][j]);        }    }    PR(MCMF(s,t));}