Tour

1
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4

42

题意：

给出n个点m条单向边边以及经过每条边的费用，让你求出走过一个哈密顿环（除起点外，每个点只能走一次）的最小费用。题目保证至少存在一个环满足条件。

解析：

任意类似的【有向环最小权值覆盖】问题，都可以用最小费用流来写。

由于题目中要求每个点最多走一次，为了防止走多次的发生，我们要把每个点 i 拆成左点i 和 右点i + n两个点。

具体建图如下:

源点outset编号0, 所有左点编号 1~n ，右点编号 n+1 ~ 2*n, 汇点inset 编号 2*n+1.
（1）源点outset到第i个点有边 ( outset, i, 1, 0)，即源点和左点建边。
（2）如果从 i 点到 j 点有权值为 c 的边,那么有边  (i,  j+n,  1,  c)，即左点和右点建边， 确保了每个点只走一次。
（3）每个节点到汇点有边 (i+n,  inset,  1,  0)， 即右点和汇点建边。

最终如果最大流 == n 的话（即满流），那么最小费用就是我们所求，这里题目确保有解，所以下面的代码我就没判断。

为什么这样的构图方法就可以求得我们所要的解， 具体解析请点这里：解析

而且本题时间要求比较严格，各种超时，需要加个去重边处理才行。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define maxn 500
#define maxm 77000
using namespace std;
int n, m;
int outset;//超级源点
int inset;//超级汇点
struct node {
    int u, v, cap, flow, cost, next;
};

node edge[maxm];
int head[maxn], cnt;
int per[maxn];//记录增广路径上 到达点i的边的编号
int dist[maxn], vis[maxn];

void init(){
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, int w, int c){
    int i;
    for(i = head[u]; i != -1; i = edge[i].next){
        node E = edge[i];
        if(v == E.v)
            break;
    }
    if(i != -1){
        if(edge[i].cost > c)
            edge[i].cost = c, edge[i ^ 1].cost = -c;
        return ;
    }
    //edge[cnt] = {u, v, w, 0, c, head[u]}这样写就直接超时了，晕+_+
    node E1 = {u, v, w, 0, c, head[u]};
    edge[cnt] = E1;
    head[u] = cnt++;
    node E2 = {v, u, 0, 0, -c, head[v]};
    edge[cnt] = E2;
    head[v] = cnt++;
}


void getmap(){
    scanf("%d%d", &n, &m);
    outset = 0;
    inset = n * 2 + 1;
    for(int i = 1; i <= n; ++i){
        add(outset, i, 1, 0);
        add(i + n, inset, 1, 0);
    }
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b + n, 1, c);
    }
}

bool SPFA(int st, int ed){
    queue<int>q;
//    memset(dist, INF, sizeof(dist));
//    memset(vis, 0, sizeof(vis));
//    memset(per, -1, sizeof(per));
    for(int i = 0; i <= inset; ++i){
        dist[i] = INF;
        vis[i] = 0;
        per[i] = -1;
    }
    dist[st] = 0;
    vis[st] = 1;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next){
            node E = edge[i];
            if(dist[E.v] > dist[u] + E.cost && E.cap > E.flow){//可以松弛 且 没有满流
                dist[E.v] = dist[u] + E.cost;
                per[E.v] = i;//记录到达这个点的边的编号
                if(!vis[E.v]){
                    vis[E.v] = 1;
                    q.push(E.v);
                }
            }
        }
    }
    return per[ed] != -1;
}

void MCMF(int st, int ed, int &cost, int &flow){
    flow = 0;//总流量
    cost = 0;//总费用
    while(SPFA(st, ed)){//每次寻找花销最小的路径
        int mins = INF;
        for(int i = per[ed]; i != -1; i = per[edge[i ^ 1].v]){
            mins = min(mins, edge[i].cap - edge[i].flow);
        }
         //增广
        for(int i = per[ed]; i != -1; i = per[edge[i ^ 1].v]){
            edge[i].flow += mins;
            edge[i ^ 1].flow -= mins;
            cost += edge[i].cost * mins;
        }
        flow += mins;
    }
}
int main (){
    int T;
    scanf("%d", &T);
    while(T--){
        init();
        getmap();
        int cost, flow;
        MCMF(outset, inset, cost, flow);
        printf("%d\n", cost);
    }
    return 0;
}

HDU 3488--Tour【最小费用最大流 && 有向环最小权值覆盖 && 经典】

原文：http://blog.csdn.net/hpuhjh/article/details/48038225