题目大意
一个图上有N个顶点，从1到N标号，顶点之间存在一些无向边，边有长度，要求从顶点1走到顶点N，再从顶点N走回顶点1，其中不必要经过每个顶点，但是要求走的路径上的边只能经过一次。求出从1--->N-->1的路径的长度最小值。
题目分析
每条无向边最多只能走一次，可以视为这些边的容量只有1。题目中要求从顶点1走到N再走回顶点1，其中经过的边只能走一次，其实可以看做从顶点1出发的两条不同的路径（路径的边不能有重合）到达顶点N。那么就可以视为，从顶点1出发到达顶点N的总流量为2. 题目要求总路径长度最小值，可以将路径长度视为网络流费用，则问题转化为求解最小费用最大流。
引入源点ss和汇点tt，ss引入一条边到顶点1，容量为2，费用为0；从顶点N引入一条边到tt，容量为2，费用为0。则问题就成了求从ss出发到达tt的最小费用最大流。
由于边为无向边，因此在添加边的时候，u-->v和v-->u都要添加，且添加相应的反向边（即实际图中(u，v)边在网络流图中上有4条边对应）。
实现(c++)
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define INFINITE 1 << 26
#define MAX_NODE 1005
#define MAX_EDGE_NUM 40005
struct Edge{
int to;
int vol;
int cost;
int next;
};
Edge gEdges[MAX_EDGE_NUM];
int gHead[MAX_NODE];
int gPre[MAX_NODE];
int gPath[MAX_NODE];
int gDist[MAX_NODE];
int gEdgeCount;
void InsertEdge(int u, int v, int vol, int cost){
gEdges[gEdgeCount].to = v;
gEdges[gEdgeCount].vol = vol;
gEdges[gEdgeCount].cost = cost;
gEdges[gEdgeCount].next = gHead[u];
gHead[u] = gEdgeCount++;
gEdges[gEdgeCount].to = u;
gEdges[gEdgeCount].vol = 0; //vol为0，表示开始时候，该边的反向不通
gEdges[gEdgeCount].cost = -cost; //cost 为正向边的cost相反数，这是为了
gEdges[gEdgeCount].next = gHead[v];
gHead[v] = gEdgeCount++;
}
//假设图中不存在负权和环,SPFA算法找到最短路径/从源点s到终点t所经过边的cost之和最小的路径
bool Spfa(int s, int t){
memset(gPre, -1, sizeof(gPre));
memset(gDist, 0x7F, sizeof(gDist));
gDist[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()){//由于不存在负权和环，因此一定会结束
int u = Q.front();
Q.pop();
for (int e = gHead[u]; e != -1; e = gEdges[e].next){
int v = gEdges[e].to;
if (gEdges[e].vol > 0 && gDist[u] + gEdges[e].cost < gDist[v]){
gDist[v] = gDist[u] + gEdges[e].cost;
gPre[v] = u; //前一个点
gPath[v] = e;//该点连接的前一个边
Q.push(v);
}
}
}
if (gPre[t] == -1) //若终点t没有设置pre，说明不存在到达终点t的路径
return false;
return true;
}
int MinCostFlow(int s, int t){
int cost = 0;
int flow = 0;
while (Spfa(s, t)){
int f = INFINITE;
for (int u = t; u != s; u = gPre[u]){
if (gEdges[gPath[u]].vol < f)
f = gEdges[gPath[u]].vol;
}
flow += f;
cost += gDist[t] * f;
for (int u = t; u != s; u = gPre[u]){
gEdges[gPath[u]].vol -= f; //正向边容量减少
gEdges[gPath[u]^1].vol += f; //反向边容量增加
}
}
return cost;
}
int main(){
int n, m, u, v, d;
while (scanf("%d %d", &n, &m) != EOF){
gEdgeCount = 0;
memset(gHead, -1, sizeof(gHead));
InsertEdge(0, 1, 2, 0);
for (int i = 0; i < m; i++){
scanf("%d %d %d", &u, &v, &d);
InsertEdge(u, v, 1, d);
InsertEdge(v, u, 1, d);
}
InsertEdge(n, n + 1, 2, 0);
int ans = MinCostFlow(0, n + 1);
printf("%d
", ans);
}
return 0;
}