本文共 2430 字，大约阅读时间需要 8 分钟。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4411
题目大意：从0开始按1到N的顺序，遍历所有的点，并回到0点；
解题思路：费用流！
#include<iostream>
#include<string.h> #include<stdio.h> #include<queue> using namespace std; #define MAXN 205 #define MAXE 16005 #define INF 1000000 queue<int> que; int g[MAXN][MAXN]; struct{ int node, cap, cost, next; }edge[MAXE]; int ans, cnt, n; int head[MAXN]; int pre[MAXN], dis[MAXN]; bool vis[MAXN]; void addEdge(int u, int node, int ca, int co){ edge[cnt].node = node; edge[cnt].cap = ca; edge[cnt].cost = co; edge[cnt].next = head[u]; head[u] = cnt ++; edge[cnt].node = u; edge[cnt].cap = 0; edge[cnt].cost = -co; edge[cnt].next = head[node]; head[node] = cnt ++; } bool spfa(){ // 源点为0，汇点为n。 int i, u = 0; memset(vis, 0, sizeof(vis)); while(!que.empty())que.pop(); for(i = 1; i <= n; i++)dis[i] = INF; dis[0] = 0; que.push(0); vis[0] = true; while(!que.empty()){ // 这里最好用队列，有广搜的意思，堆栈像深搜。 int u = que.front(); que.pop(); for(vis[u] = false,i = head[u]; ~i; i = edge[i].next){ int node = edge[i].node; if(edge[i].cap && dis[node] > dis[u] + edge[i].cost){ dis[node] = dis[u] + edge[i].cost; pre[node] = i; if(!vis[node]){ vis[node] = true; que.push(node); } } } } if(dis[n] == INF) return false; return true; } void end(){ int u, p, sum = INF; for(u = n; u != 0; u = edge[p^1].node){ p = pre[u]; sum = min(sum, edge[p].cap); } //maxflow += sum；//求最大流 for(u = n; u != 0; u = edge[p^1].node){ p = pre[u]; edge[p].cap -= sum; edge[p^1].cap += sum; ans += sum * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。 } } void floyd(int N) { int i, j, k; for(k = 0; k <= N; k++) for(i = 0; i <= N; i++) { for(j = 0; j <= N; j++) { if(g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[j][i] = g[i][k] + g[k][j]; } } return ; } int main(){ int N, M, K, i, j, s, t, a, b, c; while(scanf("%d%d%d", &N, &M, &K)&&(N + M + K)) { for(i = 0; i <= N; i++) { g[i][i] = 0; for(j = i + 1; j <= N; ++ j ) g[i][j] = g[j][i] = INF; } while(M--) { scanf("%d%d%d", &a, &b, &c); if(g[a][b]>c)g[a][b] = g[b][a] = c; } floyd(N); s = 0,t = 2 * N + 2; cnt = 0; memset(head, -1, sizeof(head)); for(i = 0; i <= N; i++) { if(i)addEdge(i, N + i + 1, 1, -INF); else addEdge(i, N + i + 1, K, 0); for(j = i + 1; j <= N; ++ j ) addEdge(N + i + 1, j, INF, g[i][j]); } for(i = 0; i <= N; i++) addEdge(i + N + 1, t, INF, g[0][i]); ans = 0;//ans为最小费用 //maxflow = 0； n = t; while(spfa()) end(); printf("%d\n", ans + N * INF); } return 0; } /* 1 1 1 0 1 1 3 4 2 0 1 3 0 2 4 1 3 2 2 3 2 0 0 0 */转载地址：http://feuvi.baihongyu.com/