问题描述

当FJ的朋友们来农场拜访时，他喜欢带他们参观。他的农场由N（1 ≤ N ≤ 1000）块田地组成，编号为1到N，其中1号田地是他的房子，N号田地是大谷仓。共有M（1 ≤ M ≤ 10000）条路径以不同方式连接这些田地。每条路径连接两块不同的田地，并且具有一个非零的长度（小于35,000）。

为了以最佳方式展示他的农场，他会进行一次游览：从房子出发，可能会经过一些田地，最终到达谷仓。之后，他再返回房子（可能经过一些田地）。

他希望这次游览尽可能短，但不想重复走过任何一条路径。请计算可能的最短游览路线。FJ确信对于任何给定的农场都存在这样的游览路线。

输入格式

• 第一行：两个用空格分隔的整数N和M。
• 接下来的M行：每行包含三个用空格分隔的整数，表示一条路径的起始田地、结束田地和路径长度。

输出格式

• 一行，包含最短游览路线的长度。

示例输入

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

示例输出

6

来源

USACO 2003年2月Green组

题意分析

农夫FJ要带领朋友参观他的农场，农场有 $N$ 块田地，编号从 1 到 $N$，其中 1 号田地是房子，$N$ 号田地是谷仓。农场里有 $M$ 条路径连接不同的田地，每条路径有其对应的长度。

FJ的参观行程是从房子出发，经过一些田地到达谷仓，然后再从谷仓返回房子，并且要求在整个行程中不重复经过任何一条路径。需要计算出满足该条件的最短参观路线的长度。

解题思路

本题可以将其转化为最小费用最大流问题来求解，具体步骤如下：

1. 构建网络流模型：
   • 把每一条路径看作网络中的一条边，路径的长度作为该边的费用，边的容量设为 1（保证每条路径只走一次）。
   • 引入源点 $S$ 和汇点 $T$，从源点 $S$ 向 1 号田地（房子）连一条容量为 2、费用为 0 的边，这是因为要从房子出发并返回房子，相当于有两条“流量”从房子流出和流入。
2. 使用最小费用最大流算法求解：
   • 利用 SPFA 算法寻找从源点到汇点的最短增广路径。
   • 沿着找到的增广路径更新流量和费用，不断重复这个过程，直到无法再找到增广路径为止。
3. 计算最短游览路线长度：
   • 最终的最小费用就是最短游览路线的长度。

算法标签

• 最小费用最大流：用于解决在满足流量需求的情况下，使总费用最小的问题。
• SPFA（Shortest Path Faster Algorithm）：一种用于寻找最短路径的算法，在本题中用于在网络流中寻找增广路径。

代码实现

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int inf=1e10;
const int N=1e6;
struct node{int y,v,w,n;}e[N];
int lin[N],d[N],v[N],incf[N],pre[N],len=1,S,T,n,m,x,y,w,ans=0;
void read(int x,int y,int v,int w)
{e[++len].y=y,e[len].v=v,e[len].w=w,e[len].n=lin[x],lin[x]=len;}
void add(int x,int y,int v,int w)
{read(x,y,v,w),read(y,x,0,-w);}
bool SPFA(int S){
	memset(incf,0,sizeof(incf));
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	queue<int> q; q.push(S); d[S]=0; incf[S]=inf; v[S]=1;
	while(q.size()){
		int x=q.front();q.pop();v[x]=0;
		for(int i=lin[x];i;i=e[i].n){
			int y=e[i].y;
			if(!e[i].v)continue;
			if(d[y]>d[x]+e[i].w){
				d[y]=d[x]+e[i].w;
				incf[y]=min(incf[x],e[i].v);
				pre[y]=i;
				if(!v[y])q.push(y),v[y]=1;
			}
		}
	}
	return incf[n]>0;
}
void upd(int S){
	int x=n;
	while(x!=S){
		int i=pre[x];
		e[i].v-=incf[n];
		e[i^1].v+=incf[n];
		x=e[i^1].y;
	}
	ans+=incf[n]*d[n];
}
int main()
{
	scanf("%d%d",&n,&m); S=n+1,T=S+1;
	rep(i,1,m){scanf("%d%d%d",&x,&y,&w);add(x,y,1,w),add(y,x,1,w);}
	add(S,1,2,0);
	while(SPFA(S))upd(S);
	printf("%d",ans);
	return 0;
}