1565植物大战僵尸

Description

Input

Output

仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
Sample Input

3 2

10 0

20 0

-10 0

-5 1 0 0

100 1 2 1

100 0

Sample Output

25

HINT

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。
【大致数据规模】
约20%的数据满足1 ≤ N, M ≤ 5；
约40%的数据满足1 ≤ N, M ≤ 10；
约100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。

这道题：一个经典的最大权闭合子图问题，就是之前要把那些一定干不掉的环给topo一遍删光。
我的dinic写法太丑导致超时，后来发现dinic在深搜时可以加一句话防止多余的操作。
if(!res) dis[x] = -1;
很强的一个剪枝剪完就过了。
具体见代码。

//dinic的优化。 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;

const int N = 3005;
const int M = 300005;

int ne[M] , to[M] , cnt = 1 , C[M] , dis[N] , fir[N] , res , s , t , du[N] , r , c , score[N] , ans;
bool inq[N] , die[N];

vector<int>G[N];

int pos[55][35] , tot;

int getpos(int x ,int y) {
    return (x-1) * c + y;
}

void add(int x,int y , int z) {
    ne[++ cnt] = fir[x]; fir[x] = cnt; to[cnt] = y; C[cnt] = z;
}

#define Foreachson(i,x) for(int i = fir[x];i;i = ne[i])
#define getdirection int V = to[i];

void link(int x ,int y ,int z) {
    add(x,y,z);
    add(y,x,0);
}

bool BFS(int s ,int t) {
// cerr<<1<<endl;
    queue<int>q;
    while(!q.empty()) q.pop();
    q.push(s); 
    for(int i = 0;i <= getpos(r,c) + 1;i ++) dis[i] = -1; 
    dis[s] = 0;
    while(!q.empty()) {
        int ind = q.front(); q.pop();
        Foreachson(i,ind) if(C[i] >0 && dis[to[i]] == -1) {
            getdirection;
                dis[V] = dis[ind] + 1;
                q.push(V);
                if(V == t) return 1;
            }
    }
    return (dis[t] != -1);
}

int dfs(int x ,int fl,int t) {
    if(x == t || ! fl) return fl;
    int res = 0;
    Foreachson(i,x) if(C[i] && dis[to[i]] == dis[x] + 1) {
        getdirection;
        int it = dfs(V,min(fl,C[i]),t);
        if(it) {
            res += it;
            C[i] -= it;
            C[i ^ 1] += it;
            fl -= it;
        }
        if(!fl) break;
    }
    if(!res) dis[x] = -1;
    return res;
}

int maxflow(int s,int t) {
    int fl = 0;
    int res = 0;
    while(BFS(s,t))  {
        while(fl = dfs(s,2e7,t)) res += fl;
    }
    return res;
}

void toposort() {
    queue<int>q;
    while(!q.empty()) q.pop();
    memset(die,1,sizeof(die));
    for(int i = 1;i <= getpos(r,c);i ++) if(du[i] == 0) q.push(i);
    while(!q.empty()) {
        int ind = q.front(); q.pop();
        die[ind] = 0;
        for(int i = 0;i <(int) G[ind].size();i ++) {
            int V = G[ind][i];
            du[V] --;
            if(du[V] == 0) {
                q.push(V);
            }
        }
    }
// for(int i = 1;i <= getpos(r,c);i ++) if(die[i]) cerr<<i<<" ";puts("");
}

void build() {
    s = 0; t = getpos(r,c) + 1;
    for(int i = 1;i <= getpos(r,c);i ++) {
        if(die[i]) continue;
        if(score[i] > 0) {
            link(i,t,score[i]);
            ans += score[i];
        }
        else link(s,i, -score[i]);
        for(int j = 0;j <(int) G[i].size();j ++) {
            int V = G[i][j];
            if(die[V]) continue;
            link(i,V,2e9);
        }
    }
}

int main() {
// freopen("pvz9.in","r",stdin);
    scanf("%d%d",&r,&c);
    for(int i = 1;i <= r;i ++) {
        for(int j = 1;j <= c;j ++) {
            int num;
            int note = getpos(i,j);
            scanf("%d",&score[note]);
            scanf("%d",&num);
            if(j != 1)  {
                G[note].push_back(getpos(i,j-1));
                du[getpos(i,j-1)] ++;
            }
            for(int k = 1;k <= num;k ++) {
                int x , y;
                scanf("%d%d",&x,&y); x ++; y ++;
                G[note].push_back(getpos(x,y));
                du[getpos(x,y)] ++;
            }
        }
    }
    toposort();
    build();
    printf("%d\n", ans - maxflow(s,t));
}