P2805 [NOI2009]植物大战僵尸 (拓扑排序 + 最小割)

题意:N*M的矩阵每个点上都有一颗植物僵尸只能从每一行的最右边向左进攻

　　每个植物有攻击范围可以保护在攻击范围内的植物同时每一颗植物也保护他左边的植物

　　摧毁每个植物能获得价值如果这个植物被保护着就无法摧毁求最大收益

题解:看了题解说一个物品被若干物品保护着要摧毁它必须先摧毁保护它的东西这种模型

　　反向建边就是有向图中的闭合子图这个模型求闭合子图的最大权十分套路

　　把所有正权和源点连容量为权值大小的边把负权点和汇点连容量为权值的绝对值大小的边

　　权值等于0的点连谁都不影响然后不同点之间有边就连容量为INF的边

　　在这个图中跑一遍最小割然后用正权点权值和 - 最小割就是闭合子图的最大权了

　　但是这个题有一个坑点如果两个点互相保护那么这两个点显然就都摧毁不了所以我们要预先处理成环的点

　　先正向连边然后拓扑排序搞一搞就好了

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, m, cnt, s, t, maxflow, ans;

struct node {

    int to, nex, val;

}E[2000005];

int head[1005];

vector<int> g[1005];

int du[1005], vis[1005], val[1005];

void addedge(int x, int y, int va) {

    E[++cnt].to = y; E[cnt].nex = head[x]; head[x] = cnt; E[cnt].val = va;

    E[++cnt].to = x; E[cnt].nex = head[y]; head[y] = cnt; E[cnt].val = 0;

}

int get(int x, int y) {return (x - 1) * m + y;}

void topsort() {

    queue<int> que;

    for(int i = 1; i <= n; i++)

    for(int j = 1; j <= m; j++)

        if(!du[get(i, j)]) que.push(get(i, j)), vis[get(i, j)] = 1;

    while(!que.empty()) {

        int u = que.front();

        que.pop();

        for(int i = 0; i < g[u].size(); i++) {

            int v = g[u][i];

            du[v]--;

            if(!du[v]) que.push(v), vis[v] = 1;

        }

    }

}

int dis[1005], inque[1005], cur[1005];

bool bfs() {

    for(int i = 1; i <= t; i++) dis[i] = INF, inque[i] = 0, cur[i] = head[i];

    queue<int> que; que.push(s);

    dis[s] = 0; inque[s] = 1;

    while(!que.empty()) {

        int u = que.front();

        que.pop();

        inque[u] = 0;

        for(int i = head[u]; i; i = E[i].nex) {

            int v = E[i].to;

            if(E[i].val && dis[v] == INF) {

                dis[v] = dis[u] + 1;

                if(!inque[v]) {

                    que.push(v);

                    inque[v] = 1;

                }

            }

        }

    }

    return dis[t] != INF;

}

int viss;

int dfs(int x, int flow) {

    if(x == t) {

        viss = 1;

        maxflow += flow;

        return flow;

    }

    int used = 0, rflow = 0;

    for(int i = cur[x]; i; i = E[i].nex) {

        cur[x] = i;

        int v = E[i].to;

        if(E[i].val && dis[v] == dis[x] + 1) {

            if(rflow = dfs(v, min(flow - used, E[i].val))) {

                used += rflow;

                E[i].val -= rflow;

                E[i ^ 1].val += rflow;

                if(used == flow) break;

            }

        }

    }

    if(!used) dis[x] = INF;

    return used;

}

void dinic() {

    maxflow = 0;

    while(bfs()) {

        viss = 1;

        while(viss) {

            viss = 0;

            dfs(s, INF);

        }

    }

}

int main() {

    ans = 0;

    cnt = 1;

    scanf("%d%d", &n, &m);

    s = n * m + 1; t = s + 1;

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++) {

            int pos = get(i, j);

            scanf("%d", &val[pos]);

            int w; scanf("%d", &w);

            for(int i = 1; i <= w; i++) {

                int x, y;

                scanf("%d%d", &x, &y);

                x++, y++;

                int pos1 = get(x, y);

                du[pos1]++; g[pos].push_back(pos1);

            }

            if(j != m) {

                int pos2 = pos + 1;

                du[pos]++; g[pos2].push_back(pos);

            }

        }

    topsort();

    for(int i = 1; i <= n; i++)

    for(int j = 1; j <= m; j++) {

        int pos = get(i, j);

        if(!vis[pos]) continue;

        if(val[pos] >= 0) addedge(s, pos, val[pos]), ans += val[pos];

        else addedge(pos, t, -val[pos]);

        for(int k = 0; k < g[pos].size(); k++) {

            int v = g[pos][k];

            if(vis[v]) addedge(v, pos, INF);

        }

    }

    dinic();

    //for(int i = 1; i <= n * m; i++) cout << vis[i] << endl;

    //cout << ans << " " << maxflow << endl;

    printf("%d\n", ans - maxflow);

    return 0;

}

巴特西

P2805 [NOI2009]植物大战僵尸 (拓扑排序 + 最小割)

最新文章

热门文章