题解 P4542 【[ZJOI2011]营救皮卡丘】

· · 题解

这里是完完全全低人一等的垃圾做法。

首先先说一下自己的思路：因为击败位置 i 的人只能经过前 i 个点，因此就有这样一种思路：建立 n 层的图，第 i 层节点数是 i，即前 i 个点。用 (i,j) 表示第 i 层的第 j 个点。则，我们连边 \Big((i,j),(i+1,j),\infty,0\Big)，用来表示那些不击败位置 i 的人；而对于连接 (i,i) 与 (i+1,i) 的边，我们用上下界网络流限制这条边必须流经。然后，在每层里面，我们仅连原图中两端点均 \leq i 的边。此方法正确性显然，但是粗略估计一下，每层都要连 m 条边，一共 n 层，点数 n^2，边数 nm=n^3，怎么想都不可能过罢。

但是发现，我们可以把每个人都留到它击败某层的位置的时候再走。具体而言，在第 i 层，我们不连接全部 m 条边，而是对于 j<i，连接 \Big((i,j),(i,i),\infty,dis_{i,j}\Big)，表示仅考虑 \leq i 的边的最短路，或者说以 i 为根的最短路径树。显然，此方法点数 n^2，边数 n^2，硬上，过了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,p,s,t,tot,DIS[210][210],num[210][210];
namespace MCMF{
    const int N=12000;
    const int M=7000000;
    int head[N],cnt,deg[N],id[N],S,T,dis[N],cost;
    struct edge{int to,next,val,cost;}edge[M];
    void ae(int u,int v,int w,int c){
//      printf("%d %d (%d,%d)\n",u,v,w,c);
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    void ae(int u,int v){deg[u]--,deg[v]++;}
    queue<int>q;
    bool in[N];
    bool SPFA(){
        q.push(S),memset(dis,0x3f,sizeof(dis)),dis[S]=0,in[S]=true;
        while(!q.empty()){
            int x=q.front();q.pop(),in[x]=false;
            for(int i=head[x],y;i!=-1;i=edge[i].next)if(edge[i].val&&dis[y=edge[i].to]>dis[x]+edge[i].cost){
                dis[y]=dis[x]+edge[i].cost,id[y]=i;
                if(!in[y])in[y]=true,q.push(y);
            }
        }
        if(dis[T]==0x3f3f3f3f)return false;
        int mn=0x3f3f3f3f;
        for(int x=T;x!=S;x=edge[id[x]^1].to)mn=min(mn,edge[id[x]].val);
        cost+=mn*dis[T];
        for(int x=T;x!=S;x=edge[id[x]^1].to)edge[id[x]].val-=mn,edge[id[x]^1].val+=mn;
        return true;
    }
}
using namespace MCMF;
int main(){
    scanf("%d%d%d",&n,&m,&p),memset(DIS,0x3f,sizeof(DIS)),memset(head,-1,sizeof(head));
    for(int i=0;i<=n;i++)DIS[i][i]=0;
    for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),DIS[x][y]=DIS[y][x]=min(DIS[x][y],z);
    for(int i=0;i<=n;i++)for(int j=0;j<=i;j++)num[i][j]=++tot;
    s=++tot,t=++tot,S=++tot,T=++tot;
    ae(s,num[0][0],p,0);
    for(int k=0;k<=n;k++){
        for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)DIS[i][j]=min(DIS[i][j],DIS[i][k]+DIS[k][j]);
        for(int i=0;i<=k;i++)ae(num[k][i],num[k][k],0x3f3f3f3f,DIS[i][k]),ae(num[k][i],t,0x3f3f3f3f,0);
        if(k<n){
            for(int i=0;i<=k;i++)ae(num[k][i],num[k+1][i],0x3f3f3f3f,0);
            ae(num[k][k],num[k+1][k]);
        }
    }
    ae(num[n][n],t);
    ae(t,s,0x3f3f3f3f,0);
    for(int i=1;i<=t;i++){
        if(deg[i]>0)ae(S,i,deg[i],0);
        if(deg[i]<0)ae(i,T,-deg[i],0);
    }
    while(SPFA());
    printf("%d\n",cost);
    return 0;
}

然后是正解。正解只需要观察到可以把问题转换成 k 个人，每个人击败的位置递增，且两两人的位置集合无交即可。于是问题转换为DAG上路径覆盖问题，随便拆点就完事了。代码咕了