POJ2135FarmTour（最小费用最大流模板题）

Description

Input

Output

Sample Input

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

Sample Output

6

Source

给出一个无向图，其中有n个点，m条边，要从1号区域走到n号区域，去的时候和回来的时候不能走一条重复的边。问这一去一回的最小花费。

思路：

首先是建边。因为是无向图，所以：

那么一去一回，其实可以考虑为两次去。

①每一次加入的边，都要双向建立，费用流沿用了最大流中的退回边，正向边建立的费用是w.退回边建立的费用是-w。因为要求的是每一条边只经过一次不重复，那么其流量限制就是1.

②建立S源点连入1号节点，没有花费，流量为2。表示要去两次N号节点。

②建立T汇点，从N号节点连入，同样没有花费，流量为2，表示要走到N号节点两次。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e3 + 7;
const int maxv = 200005;
const int INF = 0x3f3f3f3f;
int head[maxn], dis[maxn], path[maxn], pre[maxn], book[maxn] , n, m, s, t, k, sum;
struct node
{
    int v, w, f, next, cnt;
}edge[3000005];
void addEdge(int u, int v, int w, int f)
{
    edge[k].v = v;
    edge[k].w = w;
    edge[k].f = f;
    edge[k].cnt = k;
    edge[k].next = head[u];
    head[u] = k++;
    edge[k].v = u;
    edge[k].w = -w;
    edge[k].f = 0;
    edge[k].cnt = k;
    edge[k].next = head[v];
    head[v] = k++;
}
int spfa()
{
    queue q;
    q.push(s);
    memset(pre, -1, sizeof(pre));
    memset(path, -1, sizeof(path));
    for(int i = 1; i <= t; i++) dis[i] = INF;
    dis[s] = 0;
    memset(book, 0, sizeof(book));
    book[s] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        book[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int to = edge[i].v;
            int w = edge[i].w;
            int f = edge[i].f;
            if(f && dis[to] > dis[u] + w)
            {
                dis[to] = dis[u] + w;
                pre[to] = u;
                path[to] = edge[i].cnt;
                if(!book[to])
                {
                    q.push(to);
                    book[to] = 1;
                }
            }
        }
    }
    if(dis[t] != INF) return 1;
    else return 0;
}
void Min_costflow()
{
    int ans = 0;
    int maxflow = 0;
    while(spfa())
    {
        int minx = INF;
        for(int i = t; i != s; i = pre[i])
        {
            minx = min(minx, edge[path[i]].f);
        }
        maxflow += minx;
        ans += dis[t]*minx;
        for(int i = t; i != s; i = pre[i])
        {
            edge[path[i]].f -= minx;
            edge[path[i]^1].f += minx;
        }
    }
    printf("%d\n", ans);
}
int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        s = 0, t = n+1, k = 0;
        memset(head, -1, sizeof(head));
        int x, y, z;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            addEdge(x, y, z, 1);
            addEdge(y, x, z, 1);
        }
        addEdge(s, 1, 0, 2);
        addEdge(n, t, 0, 2);
        Min_costflow();
    }
    return 0;
}