HDU6598-Harmonious Army(网络流+最小割+二元费用问题)

题目链接:HDU6598-Harmonious Army

题意:

有n个士兵,m对关系,每个士兵都可以选择其职业(法师和战士),若一对关系中的两个士兵同时选择战士,收益为A,同时选择法师的收益为C,其他情况的收益为B,为你最大收益。

题解:

二元费用问题。
1.png
2.png

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 1e3;
const int MAXM = 1e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
int T;
int n, m;
struct EDGE
{
    int v, nxt;
    ll w;
} edge[MAXM << 1];
int ecnt = 0, fir[MAXN];
IL void addedge(int u, int v, ll w)
{
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int cur[MAXN], depth[MAXN];
IL int dfs(int u, ll flow, int st, int ed)
{
    if (u == ed)
        return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        ll w = edge[i].w;
        if (depth[v] == depth[u] + 1 && w != 0)
        {
            ll di = dfs(v, min(flow, w), st, ed);
            if (di)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
IL bool bfs(int st, int ed)
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    memset(depth, 0, sizeof(depth));
    depth[st] = 1;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            ll w = edge[i].w;
            if (depth[v] == 0 && w)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    if (depth[ed] > 0)
        return 1;
    else
        return 0;
}
IL ll dinic(int st, int ed)
{
    ll tot = 0;
    while (bfs(st, ed))
    {
        for (int i = 0; i <= n + 1; i++)
            cur[i] = fir[i];
        while (double temp = dfs(st, inf, st, ed))
            tot += temp;
    }
    return tot;
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        memset(fir, -1, sizeof(fir));
        ecnt = 0;
        int st = 0, ed = n + 1;
        ll sum = 0;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            ll a, b, c;
            scanf("%d%d%lld%lld%lld", &u, &v, &a, &b, &c);
            sum += a + b + c;
            addedge(st, u, (a + b)), addedge(u, st, 0);
            addedge(st, v, (a + b)), addedge(v, st, 0);
            addedge(u, ed, (b + c)), addedge(ed, u, 0);
            addedge(v, ed, (b + c)), addedge(ed, v, 0);
            addedge(u, v, (a + c) - b * 2), addedge(v, u, 0);
            addedge(v, u, (a + c) - b * 2), addedge(u, v, 0);
        }
        ll ans = dinic(st, ed);
        ans = sum - ans / 2;
        printf("%lld\n", ans);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。