自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 21:38:03，当前版本为作者最后更新于2020-01-06 21:56:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

广告：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$ 的边。

$BUG$：一条路径的费用（长度）会被算多遍。

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$ 的边。

$BUG$:费用流算法跑不了有负权边的图。

正解：

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

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

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

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

连边：拆 $i$ 点为 $i_x$ 和 $i_y$

1. $s\to 1_x\sim n_x$ 流量 $1$ ，费用 $0$（相当于星球上的等待者） 。

2. $s\to 1_y\sim n_y$ 流量 $1$ ，费用 $a_i$（相当于能力爆发模式）。

3. $1_y\sim n_y\to t$ 流量 $1$ ，费用 $0$（相当于打卡）。

4. $u_x\to v_y$ 流量 $1$ ，费用 $w$（相当于星际航路）。

以下是代码 $+$ 注释

#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;
}

网络流题重在思考。

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

谢谢大家! !