题目描述
输入格式
输出格式
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为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;
}
No Leanote account ? Sign up now.