网络流/最大权闭合子图+拓扑排序
感动死了>_<，一年多以前刚知道网络流的时候听说了这道名字很带感的题目，现在终于有实力切掉它了。
这题是最大权闭合子图模型的经典应用<_<，首先我们看到有正权有负权，有些点之间还有依赖关系（保护/左右顺序）
对于每个点，我们向它直接保护的点连边（它左边的第一个点也视为被它保护），表示必须先吃掉这棵植物才能吃后面的，然后进行拓扑排序，对于满足拓扑关系的x->y我们建弧y->x，容量为INF，表示如果要选y就必须选x，同时对所有拓扑排序能排到的点（不在环里的点）向S/T建弧（按权值正负）。然后跑最大流即可。
/**************************************************************
Problem: 1565
User: Tunix
Language: C++
Result: Accepted
Time:2016 ms
Memory:8000 kb
****************************************************************/ //BZOJ 1565
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,tot,ans,Sum,in[N],a[N];
inline int pack(int i,int j){
return (i-)*m+j;
}
struct edge{int to,v;};
struct Net{
edge E[M];
int head[N],next[M],cnt;
void ins(int x,int y,int v){
E[++cnt]=(edge){y,v};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int v){
ins(x,y,v); ins(y,x,);
}
vector<int>G[N];
int S,T,cur[N],d[N],Q[N];
bool mklevel(){
F(i,S,T) d[i]=-;
d[S]=;
int l=,r=-;
Q[++r]=S;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[T]!=-;
}
int dfs(int x,int a){
if (x==T) return a;
int flow=;
for(int &i=cur[x];i && flow<a;i=next[i])
if (E[i].v && d[E[i].to]==d[x]+){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()){
F(i,S,T) cur[i]=head[i];
ans+=dfs(S,INF);
}
}
void top_sort(){
int l=,r=-;
F(i,,tot) if(in[i]==){
Q[++r]=i;
if (a[i]>) {add(S,i,a[i]); Sum+=a[i];}
else add(i,T,-a[i]);
}
while(l<=r){
int x=Q[l++];
rep(i,G[x].size()){
int y=G[x][i];
add(y,x,INF);
in[y]--;
if (in[y]==){
if (a[y]>){ add(S,y,a[y]); Sum+=a[y];}
else add(y,T,-a[y]);
Q[++r]=y;
}
}
}
}
void init(){
n=getint(); m=getint(); cnt=;
tot=n*m; S=; T=tot+; Sum=ans=;
int x,y,p;
F(i,,n) F(j,,m){
a[pack(i,j)]=getint();
p=getint();
F(k,,p){
x=getint()+; y=getint()+;
G[pack(i,j)].pb(pack(x,y));
in[pack(x,y)]++;
}
if (j>){
G[pack(i,j)].pb(pack(i,j-));
in[pack(i,j-)]++;
}
}
top_sort();
Dinic();
printf("%d\n",Sum-ans);
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("1565.in","r",stdin);
freopen("1565.out","w",stdout);
#endif
G1.init();
return ;
}
1565: [NOI2009]植物大战僵尸
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1619 Solved: 756
[Submit][Status][Discuss]
Description
Input
Output
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
Sample Input
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
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 。