题解 P4237 【荒芜的海洋】

Tweetuzki · 2018-02-17 09:46:33 · 题解

最小费用最大流。

租每一个雇佣兵，我们就从超级源向这个雇佣兵所在岛屿连一条容量为1（因为只能雇佣一次），费用为该雇佣兵价格的边。

对于每座桥，我们看作是一条连接点的无向边。则从该桥两边向彼此连一条容量为INF，费用为该桥长度的边。

对于每座岛上的野兽，我们可以拆点。把该岛拆成入点和出点，入点向出点连一条容量为INF，费用为该岛野兽数量的边。

对于每一个奖赏，都向超级汇连一条长度为1（因为只能取一次），费用为0的边。

最后求解最小费用最大流即可。

若最大流流量小于宝藏数量，则无法获得所有的奖赏。输出最大流的流量。

否则可以获得所有的宝藏。输出所有奖赏的诱惑力减去最小费用。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> P;

const int MAXN = 2001, MAXM = 15000, INF = 0x7F7F7F7F;

struct edge {
    int to, cap, cost, rev;
};

int n, m, a, b, sum;
vector <edge> G[MAXN + 1];

edge make_edge(int to, int cap, int cost, int rev) {
    edge x;
    x.to = to, x.cap = cap, x.cost = cost, x.rev = rev;
    return x;
}

void add_edge(int from, int to, int cap, int cost) {
    G[from].push_back(make_edge(to, cap, cost, G[to].size()));
    G[to].push_back(make_edge(from, 0, -cost, G[from].size() - 1));
}

void init() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        add_edge(i, i+n, INF, x);
    }
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u + n, v, INF, w);
        add_edge(v + n, u, INF, w);
    }
    for (int i = 1; i <= a; ++i) {
        int q, p;
        scanf("%d %d", &q, &p);
        add_edge(0, p, 1, q);
    }
    for (int i = 1; i <= b; ++i) {
        int k, q;
        scanf("%d %d", &k, &q);
        sum += k;
        add_edge(q + n, n + n + 1, 1, 0);
    }
}

namespace EK_SPFA {
    int dis[MAXN + 1];
    int prev[MAXN + 1];
    int pree[MAXN + 1];

    void bfs(int s) {
        bool mark[MAXN + 1];
        memset(dis, 0x7F, sizeof(dis));
        memset(prev, -1, sizeof(prev));
        memset(pree, -1, sizeof(pree));
        memset(mark, 0, sizeof(mark));
        queue <int> q;
        dis[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            mark[x] = false;
            for (int i = 0; i < G[x].size(); ++i) {
                edge &e = G[x][i];
                if (e.cap > 0  &&  dis[x] + e.cost < dis[e.to]) {
                    dis[e.to] = dis[x] + e.cost;
                    prev[e.to] = x;
                    pree[e.to] = i;
                    if (!mark[e.to]) {
                        mark[e.to] = true;
                        q.push(e.to);
                    }
                }
            }
        }
    }

    P min_cost_max_flow(int s, int t) {
        int flow = 0, cost = 0;
        for(;;) {
            bfs(s);
            if (dis[t] == INF)
                return make_pair(flow, cost);
            int d = INF;
            for (int i = t; prev[i] != -1; i = prev[i])
                d = min(d, G[prev[i]][pree[i]].cap);
            flow += d;
            cost += d*dis[t];
            for (int i = t; prev[i] != -1; i = prev[i]) {
                edge &e = G[prev[i]][pree[i]];
                e.cap -= d;
                G[e.to][e.rev].cap += d;
            }
        }
    }
}

int main() {
    init();
    P ans = EK_SPFA::min_cost_max_flow(0, n + n + 1);
    if (ans.first < b) {
        puts("No");
        printf("%d\n", ans.first);
    } else {
        puts("Yes");
        printf("%d\n", sum - ans.second);
    }
    return 0;
}