Icontofig 's Blog

题目描述

输入格式

输出格式

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

样例输入

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0​

样例输出

25​

数据范围及提示

在样例中, 植物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 。

题解

首先注意到，由于僵尸是从右侧开始走的，所以同一行内右侧植物可以认为是保护左侧一个植物的，在保护关系加边的时候可以加上这类边。
很好想，我们注意到如果把植物间的保护关系建出图，那么就可以发现，其实就是个最大权闭合子图（相当于最小割）的问题，不过形成环的植物们都是无敌的，所以可以用tarjan或者topsort求出环，然后把环上的点全部删掉，剩下的跑最大权闭合子图就行了。

网络流建图方式：

把剩下的点分为两类： score大于零的：从源点S向此点连边，流量为score
score小于零的：从此点向汇点T连边，流量为-score
然后每个点向自己保护的点连一条反向边，流量为INF
最大权闭合子图的求法：跟最小割一样，把剩下的点里面正的score全加起来，减去跑的dinic返回的值（最小割），就是答案。当然此处要和0取较大值。

代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 605;
const int INF = 2147483647;
int n,m,c,b,ans = 0,ans2 = 0;
int S,T;
queue<int>q;
struct plant{
    int x,y,sc,w;
}a[maxn];
struct edge1{
    int fr,to,next;
}e[maxn*maxn];
int h[maxn],cnt = 0;
void add1(int u,int v){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].next = h[u];h[u] = cnt++;
}
struct edge2{
    int fr,to,cap,next;
}edges[maxn*maxn];
int g[maxn],sum = 0;
void add2(int u,int v,int c){
    edges[sum].fr = u;edges[sum].to = v;edges[sum].cap = c;edges[sum].next = g[u];g[u] = sum++;
    edges[sum].fr = v;edges[sum].to = u;edges[sum].cap = 0;edges[sum].next = g[v];g[v] = sum++;
}
stack<int>s;
int dfst = 0;
int dfn[maxn],low[maxn],ins[maxn],vis[maxn],scc_cnt,tot = 0,cur[maxn],d[maxn];
void dfs(int x){
    dfn[x] = low[x] = ++dfst;
    s.push(x);
    ins[x] = 1;
    for(int i = h[x];i != -1;i = e[i].next){
        if(!dfn[e[i].to]){
            dfs(e[i].to);
            low[x] = min(low[x],low[e[i].to]);
        }
        else if(ins[e[i].to])low[x] = min(low[x],dfn[e[i].to]);
    }
    if(dfn[x] == low[x]){
        scc_cnt++;
        tot = 0;
        while(true){
             int p = s.top();
             s.pop();
             ins[p] = 0;
             tot++;
             vis[x] = 1;
             if(p == x){
                 if(tot == 1)vis[x] = 0;
                 break;
             }
        }
    }
    return;
}
void tarjan(){
    for(int i = 1;i <= n*m;++i){
        if(!dfn[i])dfs(i);
    }
    return;
}
void dfs2(int now){
    for(int i = h[now];i != -1;i = e[i].next){
        if(vis[e[i].to])continue;
        vis[e[i].to] = 1;
        dfs2(e[i].to);
    }
}
void init(){
    memset(h,-1,sizeof(h));
    memset(g,-1,sizeof(g));
    n = get_num();
    m = get_num();
    for(int i = 1;i <= n*m;++i){
        a[i].x = (i-1) / m;
        a[i].y = (i-1) % m;
        a[i].sc = get_num();
        a[i].w = get_num();
        for(int j = 1;j <= a[i].w;++j){
            b = get_num();
            c = get_num();
            int id = b * m + c + 1;
            add1(i,id);
        }
        if(a[i].y != 0)add1(i,i-1);
    }
    tarjan();
    for(int i = 1;i <= n*m;++i){
        if(vis[i])dfs2(i);
    } 
    return;
}
bool bfs(){
    memset(d,-1,sizeof(d));
    d[S] = 0;
    q.push(S);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = g[x];i != -1;i = edges[i].next){
            int v = edges[i].to;
            if(d[v] == -1 && edges[i].cap > 0){
                d[v] = d[x] + 1;
                q.push(v);
            }
        }
    }
    if(d[T] == -1)return false;
    return true;
}
int DFS(int x,int a){
    if(x == T || a == 0)return a;
    int flow = 0;
    for(int& i = cur[x];i != -1;i = edges[i].next){
        int v = edges[i].to;
        if(edges[i].cap > 0 && d[v] == d[x] + 1){
            int r = min(edges[i].cap,a - flow);
            r = DFS(v,r);
            flow += r;
            edges[i].cap -= r;
            edges[i^1].cap += r;
        }
    }
    return flow;
}
int dinic(int s,int t){
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;++i)cur[i] = g[i];
        flow += DFS(s,INF);
    }
    return flow;
}
int main(){
    init();
    S = 0;
    T = n*m+1;
    for(int i = 1;i <= n*m;++i){
        if(vis[i])continue;
        if(a[i].sc > 0){
            add2(S,i,a[i].sc);
            ans += a[i].sc;
        }
        else add2(i,T,-a[i].sc);
        for(int j = h[i];j != -1;j = e[j].next)
            add2(e[j].to,i,INF);
    }
    ans2 = dinic(S,T);
    ans -= ans2;
    printf("%d\n",max(ans,0));
    return 0;
}​