[NOI2009]植物大战僵尸

(Problem Link)

注意到植物之间满足一种依赖关系,

即要攻打植物(i)必须消灭所有保护(i)的植物(j),每个植物都有一个权值,

于是我们建图,所有被保护植物(i)向保护了它的植物(j)连边,以表示选了(i)就必须要选(j)

那么我们的任务就是在图中选出最大权闭合子图。

那么你打了一遍板子,发现连样例都过不去。

怎么回事呢?

你仔细观察发现,如果植物之间保护关系形成了一个环,那么环中的植物以及被环保护的植物你就全部不能选。

于是你就先反向建边,然后拓扑排序一下,只把拓扑排序到的点之间的边建出来就可以了。

居然一遍AC...

/*
@Date    : 2019-07-28 17:31:02
@Author  : Adscn (adscn@qq.com)
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
	RG int xi=0;
	RG char ch=gc;
	bool f=0;
	while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;
	while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
	return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
	if(k<0)k=-k,putchar('-');
	if(k>=10)pi(k/10,0);
	putchar(k%10+'0');
	if(ch)putchar(ch);
}
const int MAXN=600+7;
const int MAXM=MAXN*MAXN+1e6;
const int S=MAXN-2,T=S+1;
const int inf=2147483647;
int n,m;
inline int P(int x,int y){return x*m+y;}
struct edge{
	int v,nxt,flow;
}e[MAXM<<1];
int head[MAXN],cnt;
int cur[MAXN];
inline void init(){memset(head,cnt=-1,sizeof head);}
inline void add(int u,int v,int f){e[++cnt]=(edge){v,head[u],f},head[u]=cnt;}
inline void link(int u,int v,int f){add(u,v,f),add(v,u,0);}
int dep[MAXN];
inline bool bfs()
{
	memset(dep,0,sizeof dep);
	static queue<int>Q;
	Q.push(S);
	dep[S]=1;
	while(!Q.empty())
	{
		int p=Q.front();Q.pop();
		for(int i=head[p],v;~i;i=e[i].nxt)
			if(e[i].flow&&!dep[v=e[i].v])
				dep[v]=dep[p]+1,Q.push(v);
	}
	return dep[T];
}
inline int dfs(int p,int restflow)
{
	if(p==T||restflow==0)return restflow;
	int sumflow=0;
	for(int &i=cur[p],flow,v;(~i)&&restflow;i=e[i].nxt)
		if(e[i].flow&&dep[v=e[i].v]==dep[p]+1&&(flow=dfs(v,min(restflow,e[i].flow))))
		{
			restflow-=flow,sumflow+=flow;
			e[i].flow-=flow,e[i^1].flow+=flow;
		}
	return sumflow;
}
inline int dinic()
{
	int maxflow=0;
	while(bfs())memcpy(cur,head,sizeof head),maxflow+=dfs(S,inf);
	return maxflow;
}
int score[MAXN];
vector<int>out[MAXN];
int in[MAXN];
bool vis[MAXN];
inline void topsort(void)
{
	static queue<int>Q;
	for(int i=0;i<n*m;++i)if(!in[i])Q.push(i),vis[i]=1;
	while(!Q.empty())
	{
		int p=Q.front();Q.pop();
		for(auto &&v:out[p])
			if(vis[v]==0&&(--in[v])==0)
				Q.push(v),vis[v]=1;
	}
}
int main(void)
{
	n=gi,m=gi;
	init();
	for(int i=0;i<n;++i)
		for(int j=0,now,tmp;j<m;++j)
			{
				score[now=P(i,j)]=gi,tmp=gi;
				for(int k=1,x,y;k<=tmp;++k)x=gi,y=gi,out[now].push_back(P(x,y)),++in[P(x,y)];
				if(j+1<m)out[P(i,j+1)].push_back(now),++in[now];
			}
	topsort();
	int sum=0;
	for(int i=0;i<n*m;++i)
		if(vis[i])
		{
			if(score[i]<0)link(i,T,-score[i]);
			else link(S,i,score[i]),sum+=score[i];
			for(auto && k:out[i])if(vis[k])link(k,i,inf);
		}
	pi(sum-dinic());
	return 0;
}
原文地址:https://www.cnblogs.com/LLCSBlog/p/11261850.html