洛咕P4542 [ZJOI2011]营救皮卡丘

套路题？

感觉讲不清，先写建图

把每个点拆成两个，A和B，

S->Ai流量=1费用=0，Bi->T流量=1费用=0，

Ai->Bj流量=1费用=ij最短路

还有一个特殊的s点，S->s流量k费用0

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

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

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

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)

                f[i][j]=std::min(f[i][j],f[i][k]+f[k][j]);

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

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=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=1;

il vd link(int a,int b,int c,int d){

    nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c,cost[id]=d;

    nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0,cost[id]=-d;

}

il bool Mincost(int&total){

    static int que[maxn],dist[maxn],hd,tl,inq[maxn]={0},lst[maxn]={0};

    hd=tl=0;

    memset(dist,63,sizeof dist);

    dist[S]=0;que[tl++]=S;inq[S]=1;

    while(hd^tl){

        int x=que[hd++];hd%=maxn;

        for(int i=fir[x];i;i=nxt[i])

            if(w[i]&&dist[dis[i]]>dist[x]+cost[i]){

                dist[dis[i]]=dist[x]+cost[i];lst[dis[i]]=i;

                if(!inq[dis[i]])inq[dis[i]]=1,que[tl++]=dis[i],tl%=maxn;

            }

        inq[x]=0;

    }

    if(dist[T]==dist[0])return 0;

    for(int i=lst[T];i;i=lst[dis[i^1]])--w[i],++w[i^1],total+=cost[i];

    return 1;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("4542.in","r",stdin);

    freopen("4542.out","w",stdout);

#endif

    int n=gi(),m=gi(),k=gi(),a,b,c;

    memset(f,63,sizeof f);

    for(int i=0;i<=n;++i)f[i][i]=0;

    for(int i=1;i<=m;++i)a=gi(),b=gi(),c=gi(),f[a][b]=f[b][a]=std::min(f[a][b],c);

    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)

                    f[i][j]=std::min(f[i][j],f[i][k]+f[k][j]);

    S=n*2+1,T=n*2+2,s=n*2+3;

    link(S,s,k,0);

    for(int i=1;i<=n;++i)link(S,i,1,0),link(i+n,T,1,0),link(s,i+n,1,f[0][i]);

    for(int i=1;i<=n;++i)

        for(int j=i+1;j<=n;++j)

            if(f[i][j]!=f[0][0])

                link(i,j+n,1,f[i][j]);

    int ans=0;while(Mincost(ans));

    printf("%d\n",ans);

    return 0;

}

巴特西

洛咕P4542 [ZJOI2011]营救皮卡丘

最新文章

热门文章