Hdu 6598 Harmonious Army 最小割

N个人 每个人可以是战士/法师  M个组合 每个组合两个人 同是战士+a 同是法师+c 否则+b

对于每一个u,v,a,b,c

建(S,u,a) (u,v,a+c-2*b) (v,T,c) (S,v,a) (v,u,a+c-2*b) (u,T,c)

最后答案为(2*sum(a+c)-最大流)/2

思路可以参考洛谷P1361

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = ;

const int MAXM = ;

int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], f[MAXM << ], ed = , S, T;

inline void addedge(int u, int v, int cap) {

        to[++ed] = v;

        nxt[ed] = Head[u];

        Head[u] = ed;

        f[ed] = cap;

        to[++ed] = u;

        nxt[ed] = Head[v];

        Head[v] = ed;

        f[ed] = ;

        return;

}

inline bool BFS(int x) {

        int u;

        for (int i = ; i <= x; i++)

                lev[i] = -;

        queue<int>q;

        lev[S] = ;

        q.push(S);

        while (q.size()) {

                u = q.front();

                q.pop();

                for (int i = Head[u]; i; i = nxt[i])

                        if (f[i] && lev[to[i]] == -) {

                                lev[to[i]] = lev[u] + ;

                                q.push(to[i]);

                        }

        }

        for (int i = ; i <= x; i++)

                cur[i] = Head[i];

        return lev[T] != -;

}

inline int DFS(int u, int maxf) {

        if (u == T || !maxf) {

                return maxf;

        }

        int cnt = ;

        for (int &i = cur[u], tem; i; i = nxt[i])

                if (f[i] && lev[to[i]] == lev[u] + ) {

                        tem = DFS(to[i], min(maxf, f[i]));

                        maxf -= tem;

                        f[i] -= tem;

                        f[i ^ ] += tem;

                        cnt += tem;

                        if (!maxf) {

                                break;

                        }

                }

        if (!cnt) {

                lev[u] = -;

        }

        return cnt;

}

ll Dinic(int x) {

        ll ans = ;

        while (BFS(x)) {

                ans += DFS(S, );

        }

        return ans;

}

void init(int SS, int TT) {

        for (int i = ; i <= TT; i++)

                Head[i] = ;

        ed = ;

        S = SS;

        T = TT;

        return;

}

ll answer = ;

int main() {

        int n, m;

        int u, v;

        ll a, b, c;

        while (scanf("%d %d", &n, &m) == ) {

                answer = ;

                init(, n + );

                for (int i = ; i <= m; i++) {

                        scanf("%d %d %lld %lld %lld", &u, &v, &a, &b, &c);

                        addedge(S, u, a), addedge(u, v, a + c -  * b), addedge(v, T, c);

                        addedge(S, v, a), addedge(v, u, a + c -  * b), addedge(u, T, c);

                        answer +=  * a +  * c;

                }

                printf("%lld\n", (answer - Dinic(n + )) / );

        }

        return ;

}