Description Input Output
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
最大权闭合子图。注意如果有环，那么环和环的后继是都不能选的，可以拓扑排序找出来。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int s=1005,t=1006,oo=0x3f3f3f3f;
int f1[1010],n1[2000010],t1[2000010],w1[2000010],que[1010],f[1010],
ok[1010],du[1010],out[1010],f2[1010],n2[2000010],t2[2000010],a[1010],
n,m,tot1,tot2,sum;
void a1(int u,int v,int x)
{tot1++;n1[tot1*2]=f1[u];f1[u]=tot1*2;t1[tot1*2]=v;w1[tot1*2]=x;n1[tot1*2+1]=f1[v];f1[v]=tot1*2+1;t1[tot1*2+1]=u;w1[tot1*2+1]=0;
}
void a2(int u,int v)
{du[v]++;n2[++tot2]=f2[u];f2[u]=tot2;t2[tot2]=v;
}
void init()
{int i,j,k,x,y;scanf("%d%d",&n,&m);for (i=1;i<=n;i++)for (j=1;j<=m;j++){scanf("%d%d",&a[i*m+j],&k);while (k--){scanf("%d%d",&x,&y);x++;y++;a1(x*m+y,i*m+j,oo);a2(i*m+j,x*m+y);}}for (i=1;i<=n;i++)for (j=1;j<m;j++){a1(i*m+j,i*m+j+1,oo);a2(i*m+j+1,i*m+j);}
}
void top()
{int i,j,u,v,hd=1,tl=0;/*for (int i=1;i<=t;i++)for (int j=f2[i];j;j=n2[j])printf("%d->%d\n",i,t2[j]);*/for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (du[i*m+j]==0)que[++tl]=i*m+j;while (hd<=tl){u=que[hd++];ok[u]=1;for (i=f2[u];i;i=n2[i])if (--du[v=t2[i]]==0)que[++tl]=v;}
}
void build()
{int i,j;for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (ok[i*m+j]){if (a[i*m+j]>=0){sum+=a[i*m+j];a1(s,i*m+j,a[i*m+j]);}else a1(i*m+j,t,-a[i*m+j]);}
}
bool bfs()
{int i,j,u,v,hd,tl;for (i=1;i<=n;i++)for (j=1;j<=m;j++)f[i*m+j]=0;f[t]=0;f[que[1]=s]=hd=tl=1;while (hd<=tl){u=que[hd++];for (i=f1[u];i;i=n1[i])if (w1[i]&&!f[v=t1[i]]){que[++tl]=v;f[v]=f[u]+1;}}return f[t];
}
int dfs(int u,int lim)
{if (u==t) return lim;int i,v,x,ret=0;for (i=f1[u];i&&ret<lim;i=n1[i])if (w1[i]&&f[v=t1[i]]==f[u]+1){x=dfs(v,min(lim-ret,w1[i]));w1[i]-=x;w1[i^1]+=x;ret+=x;}if (!ret) f[u]=0;return ret;
}
int solve()
{int ans=0,x;while (bfs())while (x=dfs(s,oo))ans+=x;return sum-ans;
}
int main()
{init();top();build();/*for (int i=1;i<=t;i++)for (int j=f1[i];j;j=n1[j])if (w1[j])printf("%d->%d:%d\n",i,t1[j],w1[j]);*/printf("%d\n",solve());
}