ZJOI2011 营救皮卡丘

@zryabc  August 14, 2019

题目

题目链接

思路

首先,看数据范围比较小,想到网络流。

对于最短路的那部分,在走到$j$的时候,不能经过$>j$的点,所以在$Floyd$的时候我们加一层限制$K<=j$处理出最短路。

然后考虑网络流建边。会发现有这么几个限制:

  1. 从小的点走向大的点
  2. 每个点都必须走到
  3. 不得超过$K$条路径

因为每一条路径一定都是从较小的点走向较大的点的,所以其实这是一个$DAG$。

然后考虑如何在建图中体现这些性质:

这个貌似叫作最小路径覆盖问题。

把每个点拆成入点和出点。

  1. 将$S$和$0$的出点连边,流量设为$K$,表示一开始有$K$个人从$0$点出发。
  2. 将每条路径的起点的入点向终点的出点连一条流量为$1$的边。
  3. 将每个点的出点向$T$连一条流量为$1$的边。
  4. 将$S$到每一个点的出点连一条容量为$1$的边。

这样为什么就是对的呢?笔者一开始看见这个建图也是一脸懵逼。

不妨换一个角度想:

每一条边都是一定要经过的。

也就是说每一条边都要有人去走。

至于是谁走的我们并不关心。

所以将人放在点上,再连边让其”走出去“

这样建图的目的只是为了让最大流为$n$,保证皮卡丘最终得救。

代码

#include<bits/stdc++.h>
#define M 305
using namespace std;
const int inf=1e9;
int n,m,K,s,t,tt=1,h[M];
int dis[M][M];
void Floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)
                if(k<=j&&dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)
                dis[j][i]=dis[i][j];
    }
}
struct edge{int nxt,to,co,fe;}G[M*M];
void Add(int a,int b,int c,int d){
    G[++tt]=(edge){h[a],b,c,d};h[a]=tt;
    G[++tt]=(edge){h[b],a,0,-d};h[b]=tt;
}
int ds[M],pre[M],mi[M];
bool vis[M];
queue<int>Q;
bool SPFA(){
    for(int i=s;i<=t;i++)
        vis[i]=0,ds[i]=inf;
    Q.push(s);vis[s]=1;ds[s]=0;mi[s]=inf;
    while(!Q.empty()){
        int x=Q.front();Q.pop();vis[x]=0;
        for(int i=h[x];i;i=G[i].nxt){
            int u=G[i].to,c=G[i].co,fe=G[i].fe;
            if(ds[u]>ds[x]+fe&&c){
                ds[u]=ds[x]+fe;
                pre[u]=i;
                mi[u]=min(c,mi[x]);
                if(!vis[u]){
                    vis[u]=1;
                    Q.push(u);
                }
            }
        }
    }
    return ds[t]!=inf;
}
int ans=0,ans2=0;
void Update(){
    ans+=mi[t];
    ans2+=ds[t]*mi[t];
    int x=t;
    while(x!=s){
        int i=pre[x];
        G[i].co-=mi[t];
        G[i^1].co+=mi[t];
        x=G[i^1].to;
    }
}
int main(){
    // freopen("save.in","r",stdin);
    // freopen("save.out","w",stdout);
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d%d",&n,&m,&K);n++;
    for(int i=1;i<=n;i++)dis[i][i]=0;
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);a++;b++;
        if(a>b)swap(a,b);
        dis[a][b]=dis[b][a]=min(dis[a][b],c);
    } 
    Floyd();
    s=0,t=2*n+1;
    Add(s,1,K,0);
    for(int i=2;i<=n;i++){
        Add(s,i,1,0);
        Add(i+n,t,1,0);
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(dis[i][j]<1e9)
                Add(i,j+n,1,dis[i][j]);
    while(SPFA())Update();
    printf("%d\n",ans2);
    return 0;
}

添加新评论