[文章目录]
Description
给你一张网格，每个格点上有一植物，植物有自己的分数，分数有正有负。想吃一个植物必须将其前面的植物也吃掉，并且给出有一些植物可以保护其他植物（就是说想吃一个植物，必须把保护她的植物和其前面的植物都吃掉）。问从网格的右边怎么吃才能得到最高的分数。1<=N<=20，1<=M<=30，-10000<=Score<=10000。
网络流，作一个图，被保护的植物指向保护她的植物，跑一遍最大权闭合子图。
不过，想想，金牛植物可能有无敌金身啊（环）。并且被金牛指向的植物也永远吃不了啊。并且被金牛植物指向的指向的......
再想想最大权闭合子图定义（woc？？？明摆着如果有环就要么直接都拿走，或者都撇掉）。所以，hhh，拓扑一下就好了（代码恶心）。然后再跑一遍最大权闭合子图。
我的代码建了两张图（ckh直接建立原图双向边，后向弧，标记边进行拓扑，然后标记点，bfs时直接略过不能吃的点（dis==-1），直接一张图搞定%%% %%% %%%）
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,scor[30][40],s,t,sum,ans;
queue<int>q;
int head[700],rd[700],to[600000],nxt[600000],cnt;
bool v[700];
int read()
{
char ch=getchar();int re=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*f;
}
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
void topsort()
{
for(int i=1*m+1;i<=n*m+m;i++)
if(!rd[i]) v[i]=1,q.push(i);
while(!q.empty())
{
int tmp=q.front();q.pop();
for(int y,i=head[tmp];i;i=nxt[i])
{
rd[y=to[i]]--;
if(!rd[y]){v[y]=1;q.push(y);}
}
}
}
int whead[800],wto[1200000],wnxt[1200000],wf[1200000],wcnt=1;
void add_web(int x,int y,int z)
{
wto[++wcnt]=y;
wnxt[wcnt]=whead[x];
wf[wcnt]=z;
whead[x]=wcnt;
wto[++wcnt]=x;
wnxt[wcnt]=whead[y];
wf[wcnt]=0;
whead[y]=wcnt;
}
int dis[800];
bool bfs()
{
memset(dis,-1,sizeof(dis));
while(q.size())q.pop();
q.push(s),dis[s]=0;
while(!q.empty())
{
int tmp=q.front();q.pop();
for(int y,i=whead[tmp];i;i=wnxt[i])
if(wf[i]&&dis[y=wto[i]]<0)
{
dis[y]=dis[tmp]+1;
if(y==t) return true;
q.push(y);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int k,tmp=flow;
for(int y,i=whead[x];i;i=wnxt[i])
if(wf[i]>0&&dis[y=wto[i]]==dis[x]+1)
{
k=dinic(y,min(tmp,wf[i]));
if(k==0) dis[y]=-1;//
tmp-=k;wf[i]-=k;wf[i^1]+=k;
if(tmp==0) break;
}
return flow-tmp;
}
int main()
{
cin>>n>>m;
s=n*m+m+1,t=n*m+m+2;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j!=m)
{add(i*m+j+1,i*m+j);rd[i*m+j]++;}
scor[i][j]=read();
int tmp=read();
while(tmp--)
{
int x=read(),y=read();
add(i*m+j,x*m+m+y+1);
rd[x*m+m+y+1]++;
}
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",i*m+j);
}
puts("");
}
for(int i=1*m+1;i<=n*m+m;i++)
{
printf("%d rd %d :",i,rd[i]);
for(int j=head[i];j;j=nxt[j])
printf("%d ",to[j]);
puts("");
}*/
topsort();
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",v[i*m+j]);
puts("");
}*/
for(int i=1;i<=n;i++) for(int x,j=1;j<=m;j++)
{
if(!v[i*m+j]) continue;
if(scor[i][j]>0) add_web(s,i*m+j,scor[i][j]),sum+=scor[i][j];
else add_web(i*m+j,t,-scor[i][j]);
for(int y,k=head[i*m+j];k;k=nxt[k])
{
if(!v[y=to[k]]) continue;
add_web(y,i*m+j,1<<30);
}
}
while(bfs()) ans+=dinic(s,1<<30);
printf("%d",sum-ans);
return 0;
}