NOI2009 植物大战僵尸

最大权闭合子图。

这是啥？

给一张DAG，点有点权，要求选择一个点就要选择他的所有后继，要求找一个最大的子图。

这题？

一个植物如果要被干掉，那么首先要干掉保护他的植物。

这个关系可以用一条有向边来描述。

但是这不是个DAG啊。

如果有植物互相保护，那么这些植物就无敌了。

所有要先搞出来SCC，以及由这个SCC保护的植物。

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1000;
const int_t SOURCE = 990;
const int_t SINK = 991;
const int_t INF = 0x7fffffff;
struct Edge {
    int_t from;
    int_t to;
    int_t capacity;
    int_t flow = 0;
    Edge* rev;
    bool isRev;
    Edge(int_t from, int_t to, int_t capacity) {
        this->from = from;
        this->to = to;
        this->capacity = capacity;
    }
};
std::vector<Edge*> graph[LARGE + 1];
int_t dis[LARGE + 1];
int_t curr[LARGE + 1];
bool visited[LARGE + 1];
bool onSCC[LARGE + 1];
int_t vals[LARGE + 1];
int_t inDeg[LARGE + 1];
int_t n, m;
int_t sum = 0;
int_t encode(int_t r, int_t c) { return r * m + c + 1; }
void pushEdge(int_t from, int_t to, int_t cap) {
    Edge* e0 = new Edge(from, to, cap);
    e0->isRev = false;
    Edge* e1 = new Edge(to, from, 0);
    e1->isRev = true;
    e1->rev = e0;
    e0->rev = e1;
    graph[from].push_back(e0);
    graph[to].push_back(e1);
#ifdef DEBUG
    if (cap == INF) cout << from << " " << to << endl;
        // cout << "push edge " << from << "," << to << "," << cap << endl;
#endif
}

namespace network {

bool BFS() {
    std::fill(dis + 1, dis + 1 + LARGE, INF);
    std::fill(visited + 1, visited + 1 + LARGE, false);
    std::fill(curr + 1, curr + 1 + LARGE, 0);
    std::queue<int_t> queue;
    dis[SOURCE] = 0;
    queue.push(SOURCE);
    visited[SOURCE] = true;
    while (queue.empty() == false) {
        int_t front = queue.front();
        queue.pop();
        for (auto edge : graph[front]) {
            if (edge->capacity > edge->flow && visited[edge->to] == false &&
                onSCC[edge->to] == false) {
                dis[edge->to] = dis[front] + 1;
                visited[edge->to] = true;
                queue.push(edge->to);
            }
        }
    }
    return visited[SINK];
}
int_t DFS(int_t vtx, int_t minf = INF) {
    if (minf == 0 || vtx == SINK) return minf;
    int_t result = 0;
    if (onSCC[vtx]) return 0;
    for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
        auto edge = graph[vtx][i];
        if (dis[edge->to] == dis[edge->from] + 1) {
            int_t curr =
                DFS(edge->to, std::min(minf, edge->capacity - edge->flow));
            if (curr > 0) {
                minf -= curr;
                result += curr;
                edge->flow += curr;
                edge->rev->flow -= curr;
                if (minf == 0) break;
            }
        }
    }
    return result;
}
int_t execute() {
    int_t result = 0;
    while (BFS()) {
        result += DFS(SOURCE);
#ifdef DEBUG
        cout << "arg to " << result << endl;
#endif
    }
    return result;
}
}  // namespace network

int main() {
    cin >> n >> m;
    for (int_t i = 0; i < n; i++) {
        for (int_t j = 0; j < m; j++) {
            int_t val, attacks;
            cin >> val >> attacks;
            if (j != m - 1) {
                pushEdge(encode(i, j), encode(i, j + 1), INF);
                inDeg[encode(i, j)] += 1;
            }
            for (int_t k = 1; k <= attacks; k++) {
                int_t r, c;
                cin >> r >> c;
                pushEdge(encode(r, c), encode(i, j), INF);
                inDeg[encode(r, c)] += 1;
            }
            vals[encode(i, j)] = val;
        }
    }
    std::queue<int_t> queue;
    for (int_t i = 1; i <= n * m; i++) {
        if (inDeg[i] == 0) queue.push(i);
        onSCC[i] = true;
    }
    while (queue.empty() == false) {
        int_t front = queue.front();
        queue.pop();
        onSCC[front] = false;
        for (auto edge : graph[front]) {
            if (edge->isRev) {
                inDeg[edge->to]--;
                if (inDeg[edge->to] == 0) queue.push(edge->to);
            }
        }
    }
#ifdef DEBUG
    for (int_t i = 1; i <= n * m; i++) {
        cout << "onSCC " << i << " = " << onSCC[i] << endl;
    }
#endif
    for (int_t i = 0; i < n; i++) {
        for (int_t j = 0; j < m; j++) {
            int_t val = vals[encode(i, j)];
            if (val > 0) {
                pushEdge(SOURCE, encode(i, j), val);
                if (onSCC[encode(i, j)] == false) sum += val;
            } else {
                pushEdge(encode(i, j), SINK, -val);
            }
        }
    }

#ifdef DEBUG

    cout << "sum = " << sum << endl;
#endif
    cout << sum - network::execute() << endl;
    return 0;
}