[poj][2135][Farm Tour][网络流]

题意：有N个顶点的无相图，要从点1走到N（有些点可以不走），再从N走到1，且不走重复的路，求最短的路径。

解题思路：首先从不走重复的路可以想到用边容量为1的网络流，但在这些满足条件的流中要选出路径最短，这便是最小费用流问题。建图：原图每一条边都建为双向边，容量为1，费用为路的长度。再加一个点S，与点1建2条边，容量为2，费用为0。这样求得的最大流保证有2条从1到N不相交的路，且路径最短。

#include<iostream>
using namespace std;

#define N 1010
#define M 40010
#define INF 0x3f3f3f3f
#define CLR(a, b) (memset(a, b, sizeof(a)))

int n, m;
int h[N], ev[M], nex[M], e;
int cap[M], cost[M], dist[N];
int pre[N], pree[N], cnt[N];
int stk[N], ed;
bool vis[N];

void adge(int a, int b, int c, int w){
	ev[e] = b, cost[e] = c, cap[e] = w;
	nex[e] = h[a], h[a] = e++;
	ev[e] = a, cost[e] = -c, cap[e] = 0;
	nex[e] = h[b], h[b] = e++;
}

void spfa(int s, int t, int n){
	int i, u, v;
	CLR(vis, 0), CLR(cnt, 0), CLR(dist, 0x3f);
	ed = dist[s] = 0;
	stk[ed++] = s;
	cnt[s] = 1;
	while(ed){
		u = stk[--ed]; vis[u] = 0;
		for(i = h[u]; i != -1; i = nex[i]){
			if(cap[i] <= 0) continue;
			v = ev[i];
			if(dist[v] > dist[u] + cost[i]){
				dist[v] = dist[u] + cost[i];
				pre[v] = u; pree[v] = i;
				if(!vis[v]){
					vis[v] = 1, stk[ed++] = v;
					if(++cnt[v] > n) return;
				}
			}
		}
	}
}

void mincost(int s, int t, int n, int &c, int &f){
	int u, tmp;
	c = f = 0;
	for(;;){
		spfa(s, t, n);
		if(dist[t] == INF) return;
		for(tmp = INF, u = t; u != s; u = pre[u])
			tmp = min(tmp, cap[pree[u]]);
		for(u = t; u != s; u = pre[u]){
			cap[pree[u]] -= tmp;
			cap[pree[u]^1] += tmp;
		}
		f += tmp;
		c += tmp * dist[t];
	}
}

int main(){
	int i, j;
	int c, f;
	scanf("%d%d", &n, &m);
	CLR(h, -1), e = 0;
	for(i = 0; i < m; i++){
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		adge(a, b, w, 1);
		adge(b, a, w, 1);
	}
	adge(0, 1, 0, 2);
	mincost(0, n, n + 1, c, f);
	printf("%d\n", c);
	return 0;
}

---