【传送门：BZOJ1565】
简要题意：
现在玩植物大战僵尸，与一般的植物大战僵尸的玩法不同，每个植物存在于一个图中，图中的每一个坐标都有植物，有些植物会保护一些植物，当这些植物没有被僵尸吃掉的时候，僵尸不能吃掉被保护的植物，吃掉植物会有收益或者损失，并且僵尸只能从右边往左边吃，而且只能沿直线方向吃
求出最大收益
题解：
有负权，而且还是最大收益，ok，最大权闭合子图
将保护的植物连向被保护的植物，流量为无穷大
因为僵尸只能从右边往左边吃，就相当于右边的植物保护了左边的植物，所以将右边的植物连向左边的植物，流量也是无穷大
接下来，将st连向带负权的点，流量为负权的绝对值，将带正权的点连向ed，流量为正权
这里有个问题？一般的最大权闭合子图都是st连正权，负权连ed，为什么这道题相反
原因很简单：因为对于每个被保护的植物，只有当所有保护自己的植物全部被吃掉才能被吃掉，所以这样反着连边才能使得总花费不超过总正权
还有一个坑点：
这里有可能存在一个保护环，使得环内的植物全部间接或直接受到保护，这样我们就拿这个环没办法了，就取不到环内的正权值，所以我们用拓扑排序判环，将与环相连的边去掉，再求出总正权
最后跑最大流，总正权-最大流量（最小割）就是答案了
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; struct node { int x,y,c,next,other; }a[1100000];int len,last[610]; void ins(int x,int y,int c) { int k1=++len,k2=++len; a[k1].x=x;a[k1].y=y;a[k1].c=c; a[k1].next=last[x];last[x]=k1; a[k2].x=y;a[k2].y=x;a[k2].c=0; a[k2].next=last[y];last[y]=k2; a[k1].other=k2; a[k2].other=k1; } int h[610],list[610],st,ed; bool bt_h() { memset(h,0,sizeof(h)); h[st]=1; int head=1,tail=2; list[1]=st; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==0&&a[k].c>0) { h[y]=h[x]+1; list[tail++]=y; } } head++; } if(h[ed]==0) return false; else return true; } int findflow(int x,int f) { if(x==ed) return f; int s=0,t; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==(h[x]+1)&&a[k].c>0&&f>s) { t=findflow(y,min(a[k].c,f-s)); s+=t; a[k].c-=t;a[a[k].other].c+=t; } } if(s==0) h[x]=0; return s; } struct enode { int x,y,next; }e[510000];int ee[610],elen; int c[610]; void eins(int x,int y) { elen++; e[elen].x=x;e[elen].y=y; e[elen].next=ee[x];ee[x]=elen; } int ru[610],top,sta[610]; int s;int n,m; void topsort() { top=0; for(int i=1;i<=n*m;i++) if(ru[i]==0) sta[++top]=i; while(top!=0) { int x=sta[top--]; for(int k=ee[x];k;k=e[k].next) { int y=e[k].y; ru[y]--; if(ru[y]==0) sta[++top]=y; } } for(int i=1;i<=n*m;i++) { if(ru[i]==0&&c[i]>0) s+=c[i]; } } int main() { scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); st=0;ed=n*m+1; elen=0;memset(ee,0,sizeof(ee)); memset(ru,0,sizeof(ru)); for(int i=1;i<=n*m;i++) { int k; scanf("%d%d",&c[i],&k); for(int j=1;j<=k;j++) { int x,y; scanf("%d%d",&x,&y);x++;y++; eins(i,(x-1)*m+y);ru[(x-1)*m+y]++; } } for(int i=1;i<=n;i++) { for(int j=2;j<=m;j++) { eins((i-1)*m+j,(i-1)*m+j-1); ru[(i-1)*m+j-1]++; } } s=0; topsort(); for(int i=1;i<=elen;i++) { int x=e[i].x,y=e[i].y; if(ru[x]==0&&ru[y]==0) { ins(x,y,999999999); } } for(int i=1;i<=n*m;i++) { if(ru[i]==0) { if(c[i]<0) ins(st,i,-c[i]); else ins(i,ed,c[i]); } } int ans=0; while(bt_h()) { ans+=findflow(st,999999999); } printf("%d ",s-ans); return 0; }