POJ2135 Farm Tour

这题的大意是，给出N个点和M条无向，非负权边，可能有重边，要求从点1出发到达点N，并回到点1，且每条边至多经过1次的最短路径。可以这样想，把一个环想成点1出发的两条到达点N的路径和，也就是流量为2，然后这样建图，加个超级源点与超级汇点，从超级源点到达点1的流量为2，费用为0，从点N到达超级汇点的流量为2，费用为0，然后对于其他的每条边u-v，加入u->v，流量为1，费用为权值，加入v->u，流量为1，费用为权值，然后从点1到点N，跑趟最小费用最大流就可以了。然后下面实现的邻接建图方式，对反向边的处理方便，方便实现带重边的最小费用最大流。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAX = 1005;

struct E
{
    int u, v, next, f, c;
}e[40010];
int num;
int n, m;
int head[MAX];
int S, T;
int in[MAX];
int dis[MAX];
int p[MAX];
int flow[MAX];

void addd(int u, int v, int f, int c)
{
    e[num].u = u;
    e[num].v = v;
    e[num].next = head[u];
    e[num].f = f;
    e[num].c = c;
    head[u] = num++;
}

void add(int u, int v, int f, int c)
{
    addd(u, v, f, c);
    addd(v, u, 0, -c);
}

int mcmf()
{
    memset(p, -1, sizeof(p));
    memset(in, 0, sizeof(in));
    memset(dis, -1, sizeof(dis));
    memset(flow, 0, sizeof(flow));
    dis[S] = 0;
    flow[S] = INT_MAX;
    vector<int> Q;
    in[S] = 1;
    Q.push_back(S);
    for(int i = 0; i < Q.size(); i++)
    {
        int u = Q[i];
        in[u] = 0;
        //遍历很巧
        for(int j = head[u]; j != -1; j = e[j].next)
        {
            if(e[j].f > 0 && (dis[e[j].v] == -1 || dis[u] + e[j].c < dis[e[j].v]))
            {
                dis[e[j].v] = dis[u] + e[j].c;
                flow[e[j].v] = min(flow[u], e[j].f);
                p[e[j].v] = j;
                if(in[e[j].v] == 0)
                {
                    in[e[j].v] = 1;
                    Q.push_back(e[j].v);
                }
            }
        }
    }
    return flow[T];
}

int go()
{
    int res = 0;
    while(1)
    {
        int f = mcmf();
        if(f == 0)  break;
        //很巧
        for(int i = p[T]; i != -1; i = p[e[i].u])
        {
            res += f * e[i].c;
            e[i].f -= f;
            e[i ^ 1].f += f;
        }
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    num = 0;
    memset(head, -1, sizeof(head));
    while(m--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, 1, w);
        add(v, u, 1, w);
    }
    S = 0, T = n + 1;
    add(S, 1, 2, 0);
    add(n, T, 2, 0);
    printf("%d\n", go());
}