植物大战僵尸
Description
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 。
成功获得拓扑排序的使用新姿势.jpg
其实是冲着标题去写的
思路:
很明显这是个最大权闭合子图的模型，选择了被保护的植物就必须选择保护它的植物。
然后……样例就有一个环？？？
【网络流|[BZOJ1565][NOI2009]植物大战僵尸-拓扑排序-网络流】观察后可以发现一个很明显的事实——一个环是不可摧毁的。
（popoqqq神犇的例子：想象一个无冷却的食人花面前有一个坚果）
所以，所有被环直接或间接保护的位置都不合法。直接删除就是。
那么如何删除这些点？
很简单，一个与环相连的点，在对反向边拓扑排序中的入度永远不会小于等于0。
那么对反向边拓扑排序一次，走不到的点即为需要删除的点。
对剩下的点跑网络流即可~
#include
#include
#include
#include
#includeusing namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || '9'0)
ans+=f[u];
for(int i=beg[u];
i;
i=nxt[i])
if(i&1)
{
ind[to[i]]--;
if(!ind[to[i]])
q[++r]=to[i];
}
}
}inline bool bfs()
{
memset(dis,0,sizeof(dis));
dis[s]=1;
q[r=1]=s;
l=0;
while(l!=r)
{
int u=q[++l];
for(int i=beg[u],v;
i;
i=nxt[i])
if(!dis[v=to[i]] && w[i]>0 && can[v])
{
dis[v]=dis[u]+1;
q[++r]=v;
}
}
return dis[t];
}inline int dfs(int u,int mflow)
{
if(u==t || !mflow)
return mflow;
int cost=0;
for(int i=beg[u],v,f;
i;
i=nxt[i])
if(dis[v=to[i]]==dis[u]+1 && w[i])
{
f=dfs(v,min(w[i],mflow-cost));
w[i]-=f;
w[i^1]+=f;
cost+=f;
if(cost==mflow)
break;
}
if(!cost)
dis[u]=0;
return cost;
}inline int dinic()
{
int ret=0;
while(bfs())
ret+=dfs(s,1e9);
return ret;
}inline int id(int x,int y)
{
return x*m+y+1;
}int main()
{
n=read();
m=read();
s=0,t=n*m+1;
for(int i=0;
i 
