传送门 这道题吃到某个植物a可能需要先吃掉别的植物b（在他的右边或者保护着他），那么我们把a连向b。 发现这是最大权闭合子图。 显然是可以通过网络流水过的。 闭合子图： V中顶点的所有出边均指向V内部顶点 那么按照最大权闭合图的建图方法： 1.s向正权点连流量为权值的边 2.负权点向t连流量为权值的绝对值的边 3.有边相连的两点连流量为inf的边 答案就是正权点的权值总和减去最小割。 但是数据中可能会出现氪金植物（玩家） 他们之间的保护关系像一个环（想象一个无冷却的食人花前面放一个坚果） 显然非氪金玩家僵尸是干不掉他们的。 所以在跑网络流之前先进行拓扑排序。 强制删除不可达点即可。
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #define inf 0x3f3f3f3f #define N 605 using namespace std; struct edge{int to,f,next;}e[500005]; int head[N],in[N],dis[N],f[N],q[N],ok[N]; int n,m,S,T,p,x,y,ans,tot=1; void ins(int x,int y,int w){ e[++tot].to=y; e[tot].f=w; e[tot].next=head[x]; head[x]=tot; e[++tot].to=x; e[tot].f=0; e[tot].next=head[y]; head[y]=tot; in[x]++; } void topo(){ int h=0,t=0,x; for (int i=1;i<=n*m+2;i++) if (!in[i]) q[++t]=i; while (h<t){ x=q[++h]; ok[x]=1; if (f[x]>0) ans+=f[x]; for (int i=head[x];i;i=e[i].next) if (i&1){ in[e[i].to]--; if (!in[e[i].to]) q[++t]=e[i].to; } } } bool bfs(){ int h=0,t=1,x; memset(dis,-1,sizeof(dis)); q[1]=S; dis[S]=0; while (h<t){ x=q[++h]; for (int i=head[x];i;i=e[i].next) if (dis[e[i].to]==-1&&e[i].f&&ok[e[i].to]){ dis[e[i].to]=dis[x]+1; q[++t]=e[i].to; } } return dis[T]!=-1; } int dinic(int x,int flow){ if (x==T) return flow; int rest=flow,k; for (int i=head[x];i&&rest;i=e[i].next) if (e[i].f&&dis[x]+1==dis[e[i].to]){ k=dinic(e[i].to,min(rest,e[i].f)); rest-=k; e[i].f-=k; e[i^1].f+=k; } if (rest) dis[x]=-1; return flow-rest; } int main(){ scanf("%d%d",&n,&m); S=n*m+1; T=S+1; for (int i=1;i<=n*m;i++){ scanf("%d",&f[i]); if (f[i]>0) ins(S,i,f[i]); else ins(i,T,-f[i]); scanf("%d",&p); for (int j=1;j<=p;j++){ scanf("%d%d",&x,&y); ins(x*m+y+1,i,inf); } if (i%m) ins(i,i+1,inf); } topo(); while (bfs()) ans-=dinic(S,inf); printf("%d",ans); }