Lvat_s Blog

拓扑排序消圈+最大权闭合子图

因为每次僵尸都是从右往左走，那么我们对于右往左依次连边

然后每个点的攻击集合就是相当于选了攻击集合中的点就必须选择这个点。

那么我们反向建边，因为有可能出现循环保护的情况，所以先拓扑排序消圈然后按照最大权闭合子图的模型建网络流图即可。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

int en,en1,n,m,ok[1005],cur[1005],h[1005],h1[1005],score[1005],du[1005],level[1005],S,T,now,mxval;

struct Edge{
int b,f,next,back;
}e[1000005],e1[1000005];

int Cal(int x,int y){return (x-1)*m+y;}

void AddEdge1(int sa,int sb){
e1[++en1].b=sb;
e1[en1].next=h1[sa];
h1[sa]=en1;
du[sb]++;
}

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].next=h[sa];
h[sa]=en;
}

int BFS(){
queue<int> Q;
Q.push(S);
memset(level,0,sizeof(level));
level[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(level[v] || !e[i].f)continue;
		Q.push(v);
		level[v]=level[u]+1;
	}
}
return level[T];
}

int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
	if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(!f)return flow;
	}
}
return flow-f;
}

int Dinic(){
int ans=0;
while(BFS()){
	for(int i=1;i<=T;i++)cur[i]=h[i];
	ans+=DFS(S,2100000000);
}
return ans;
}

void Toposort(){
queue<int> Q;
for(int i=1;i<=now;i++){
	if(!du[i]){ok[i]=1;Q.push(i);}
}
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h1[u];i;i=e1[i].next){
		int v=e1[i].b;
		du[v]--;
		if(!du[v]){ok[v]=1;Q.push(v);}
	}
}
}

int main(){
freopen("1565.in","r",stdin);
freopen("1565.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		int can;
		now++;
		scanf("%d %d",&score[now],&can);
        for(int k=1;k<=can;k++){
			int dx,dy;
			scanf("%d %d",&dx,&dy);
			dx++;dy++;
            AddEdge1(now,Cal(dx,dy));
        }
        if(j!=m)AddEdge1(now+1,now);
	}
}
Toposort();
S=now+1;T=now+2;
for(int i=1;i<=now;i++){
	if(ok[i]){
		if(score[i]>=0){AddEdge(S,i,score[i]);mxval+=score[i];}
		else AddEdge(i,T,-score[i]);
		for(int j=h1[i];j;j=e1[j].next){
			int v=e1[j].b;
			if(ok[v])AddEdge(v,i,2100000000);
		}
	}
}
printf("%d\n",mxval-Dinic());
return 0;
}