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 。
最大权闭合子图问题。
此类问题为：有n个点，每个点有一个权值（可以为负数），选某个点就要先选其它的一些点。求最大收益。
此类问题的一般性解法为：
1.用拓扑排序把永远选不了的点删掉。
2.若第i个点需要先选第j个点，则连一条(i,j,inf)的边。
3.如果该点点权为正，则连一条(S,i,val)的边。
4.否则连一条(i,T,-val)的边
5.最后答案为所有正权点的权值总和-最大流。
具体参见：https://www.2cto.com/kf/201611/563122.html
对于此题，显然，对于每个点，它能防御到的 每一行的最前面的点 的后面的点 都是要先选这个点的。
即设绿点能防御到所有黄点，那么要选所有红色区域就要先选绿点。
然后就做完了。
#include<iostream> #include<cstring> #include<cstdio> #define no(r,c) r*m+c+1 #define inf 2e9+7 using namespace std; int front[50];bool used[2000]; int into[2000],que[2000000],HH=0,TT=0; int h[500000],nxt[1000000],to[1000000],cap[1000000],TOT=0; int mp[50][50],x[500000],y[500000]; int S,T,level[2000],iter[2000]; void ins(int u,int v){nxt[++TOT]=h[u];h[u]=TOT;to[TOT]=v;} void ins2(int u,int v,int c){nxt[++TOT]=h[u];h[u]=TOT;to[TOT]=v;cap[TOT]=c;nxt[++TOT]=h[v];h[v]=TOT;to[TOT]=u;cap[TOT]=0;} bool bfs() { memset(level,0,sizeof(level)); int HH=0,TT=0; que[TT++]=S;level[S]=1; while(HH<TT) { int u=que[HH++]; for(int i=h[u];i;i=nxt[i]) { int v=to[i]; if(cap[i]&&!level[v]){level[v]=level[u]+1;que[TT++]=v;} } } return level[T]?true:false; } int dfs(int u,int f) { if(u==T)return f; int used=0; for(int &i=iter[u];i;i=nxt[i]) { int v=to[i];if(!cap[i]||level[v]!=level[u]+1)continue; int w=dfs(v,min(cap[i],f-used)); if(w) { cap[i]-=w;cap[i^1]+=w; used+=w;if(used==f)return f; } } return used; } int dinic() { int flow=0; while(bfs()){for(int i=1;i<=2000;i++)iter[i]=h[i];flow+=dfs(S,inf);} return flow; } int main() { int n,m,tot=0;scanf("%d%d",&n,&m);S=n*m+1,T=n*m+2; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int w;scanf("%d%d",&mp[i][j],&w); memset(front,-1,sizeof(front)); for(int k=1;k<=w;k++) { int r,c;scanf("%d%d",&r,&c); front[r]=max(front[r],c); } front[i]=max(front[i],j-1); for(int r=0;r<n;r++) for(int c=0;c<=front[r];c++){x[++tot]=no(i,j);y[tot]=no(r,c);ins(no(i,j),no(r,c));into[no(r,c)]++;} } for(int i=1;i<=n*m;i++)if(!into[i])que[TT++]=i; while(HH<=TT){int u=que[HH++];used[u]=1;for(int i=h[u];i;i=nxt[i])if(!(--into[to[i]]))que[TT++]=to[i];} memset(h,0,sizeof(h));memset(nxt,0,sizeof(nxt));memset(to,0,sizeof(to));TOT=1; int sum=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(used[no(i,j)]) if(mp[i][j]>0)ins2(S,no(i,j),mp[i][j]),sum+=mp[i][j]; else ins2(no(i,j),T,-mp[i][j]); for(int i=1;i<=tot;i++)if(used[x[i]]&&used[y[i]])ins2(y[i],x[i],inf); printf("%d",sum-dinic()); return 0; }