POJ 2135 最小费用最大流

这道题的题意就是，一个无向图，一个人从起点出发，到终点后往回走，但是走过的路不想走第二遍，也就是说必须存在两个路径从起点到终点，且这两个路径中不能有相同的边。

那么建图就比较好想了，建立一个超级源点，一个超级汇点，因为是无向图么，所以源点到点1的流量为2，费用为0，点1到源点的流量为2，费用为0，同理点n和源点，然后其他的边流量就是1，费用就是边长了。注意都是加双向边。

刚开始比较恶心的就是，我加反向负权边是手动加的，这就导致如果加边顺序不对就杯具，比如加完几条正边去加负边。然后我改了改加边的函数，让每次加边时紧挨着自动加一条反向负权边

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100005
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int tot = 0, x, y;
class mincost
{
private:
    const static int V = 2005;
    const static int E = 550000;
    const static int INF = -1u >> 1;
    struct Edge
    {
        int v, cap, cost;
        Edge *next;
    } pool[E], *g[V], *pp, *pree[V];
    int T, S, dis[V], pre[V];
    int n, m, flow, cirq[V];
    void SPFA();
    inline void addedge(int i, int j, int cap, int cost);
public:
    bool initialize(int x, int y);
    void mincost_maxflow();
};

void mincost::mincost_maxflow()
{
    while (true)
    {
        SPFA();
        if (dis[T] == INF)
            break;
        int minn = INF;
        for (int i = T; i != S; i = pre[i])
            minn = min(minn, pree[i]->cap);
        for (int i = T; i != S; i = pre[i])
        {
            pree[i]->cap -= minn;
            pool[(pree[i] - pool)^0x1].cap += minn;
            flow += minn * pree[i]->cost;

        }
        tot += minn;  //流量计算
    }
    //if(tot != x) flow = 1;
    printf("%d\n", flow);
}

void mincost::SPFA()
{
    bool vst[V] = {false};
    int tail = 0, u;
    fill(dis,dis + n,0x7fffffff);
    cirq[0] = S;
    vst[S] = 1;
    dis[S] = 0;
    for (int i = 0; i <= tail; i++)
    {
        int v = cirq[i % n];
        for (Edge *i = g[v]; i != NULL; i = i->next)
        {
            if (!i->cap)
                continue;
            u = i->v;
            if (i->cost + dis[v] < dis[u])
            {
                dis[u] = i->cost + dis[v];
                pree[u] = i;
                pre[u] = v;
                if (!vst[u])
                {
                    tail++;
                    cirq[tail % n] = u;
                    vst[u] = true;
                }
            }
        }
        vst[v] = false;
    }
}

void mincost::addedge(int i, int j, int cap, int cost)
{
    pp->cap = cap;
    pp->v = j;
    pp->cost = cost;
    pp->next = g[i];
    g[i] = pp++;
    pp->cap = 0;
    pp->v = i;
    pp->cost = -cost;
    pp->next = g[j];
    g[j] = pp++;
}
bool mincost::initialize(int x, int y)
{
    memset(g, 0, sizeof (g));
    pp = pool;
    n = x + 2;
    m = y;
    S = 0;
    T = x + 1;
    addedge(0, 1, 2, 0);
    addedge(1, 0, 2, 0);
    addedge(x, x + 1, 2, 0);
    addedge(x + 1, x, 2, 0);
    int v, u, f, c;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &c);
        addedge(v, u, 1, c);
        addedge(u, v, 1, c);
    }
    flow = 0;
    return true;
}
mincost g;
int main()
{
    while(scanf("%d%d", &x, &y) != EOF)
    {
        g.initialize(x, y);
        g.mincost_maxflow();
    }
    return 0;
}