题解 P2469 【[SDOI2010]星际竞速】

· · 题解

广告：blog

P2469 【[SDOI2010]星际竞速】

此题算法：费用流

这题难度占洛谷网络流题前10\%——Wendigo。

拿到这题时，思路真是多样，可惜全是错的，如下:

1.s\to 1\sim n 流量 1 ，1\sim n\to t 流量 1 ，中间连流量 1 费用 w_i 的路径（小编号连大编号），每个点（包括 s ）到非自己的点 i 连流量 1 费用 a_i 的边。

2.s\to mid 流量 1 ，mid\to 1_x\sim n_x 流量 1 ，1_y\sim n_y\to t 流量 1 ，i_x\to i_y 流量 1 费用 -a_i ，中间连流量 1 费用 w_i 的路径（小编号连大编号），到非自己的点 i 连流量 1 费用 a_i 的边。

正解：

想象有 n+1 个人接力跑 ，分别在点 s 和 1\sim n 上 ，开始时接力棒在 s 那个人手上。

这时候他拿着接力棒开始跑，到达某个星球后停止，把接力棒交给该星球上的选手，并打卡结束比赛。

该选手又出发，循环此过程。每个星球只可以打卡一次，必须打卡。路上走过的路程相当于费用。

最后的最大流最小费用就是答案，而原问题与此等效。

连边：拆 i 点为 i_x 和 i_y

以下是代码 + 注释

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+10;
const int M=2e6+10;
const int inf=1e8;
int d(){int x; scanf("%d",&x); return x;}
int n,m,p,s,t,a[N],fans,cans; 
struct edge{
    int adj,nex,fw,r;
}e[M];
int g[N],top=1;
void add(int x,int y,int z,int w){
    e[++top]=(edge){y,g[x],z,w};
    g[x]=top;
}
void Add(int x,int y,int z,int w){
    // printf("%d-%d %d %d\n",x,y,z,w);
    add(x,y,z,w),add(y,x,0,-w);
}
int dep[N],cur[N];
bool vis[N];
queue<int> Q;
bool spfa(){ //模板就不用说了
    for(int i=1;i<=p;i++)
        vis[i]=0,dep[i]=inf,cur[i]=g[i];
    Q.push(s),vis[s]=1,dep[s]=0;
    while(Q.size()){
        int x=Q.front(); Q.pop();
        vis[x]=0;
        for(int i=g[x];i;i=e[i].nex){
            int to=e[i].adj,d=e[i].r;
            if(e[i].fw&&dep[to]>dep[x]+d){
                dep[to]=dep[x]+d;
                if(!vis[to]){
                    vis[to]=1;
                    Q.push(to);
                }
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int x,int F){
    if(!F||x==t)
        return F;
    int flow=0,f;
    vis[x]=1;
    for(int i=cur[x];i;i=e[i].nex){
        int to=e[i].adj; cur[x]=i;
        if(!vis[to]&&dep[x]+e[i].r==dep[to]&&
        (f=dfs(to,min(F,e[i].fw)))>0){
            e[i].fw-=f;
            e[i^1].fw+=f;
            flow+=f,F-=f;
            if(!F){
                vis[x]=0;
                break;
            } 
        }
    }
    return flow;
}
int main(){
    n=d(),m=d(),p=t=2*n+2,s=t-1;
    for(int i=1,x;i<=n;i++){ //如上说明连边
        a[i]=d(); Add(i+n,t,1,0); 
        Add(s,i,1,0),Add(s,i+n,1,a[i]);
    }
    for(int i=1;i<=m;i++){
        int x=d(),y=d(),z=d();
        if(x>y) swap(x,y);
        if(z<a[y]) Add(x,y+n,1,z);
    }
    while(spfa()){ //跑最小费用最大流。
        int D=dfs(s,inf);
        fans+=D,cans+=D*dep[t];
    }
    printf("%d\n",cans);
    return 0;
}

网络流题重在思考。

写题解不易，快为博主点个赞吧。

谢谢大家! !