<题目链接>

这题是个比较经典的最大权闭合子图，可以建图转化为最小割问题，再根据最大流最小割定理，采用任意一种最大流算法求得。

对于每个点，如果点权w为正，则从源点到这个点连一条边权为w的有向边；否则如果w为负则从这个点到汇点连一条有向边。加边的时候预处理出反图的每个点入度。

其次，每一个被保护的点到保护它的点连一条边权为INF的有向边。

注意同一行的左侧点受到右侧点的间接保护，因此对于每一个不位于当前行最右的点，都要向其右侧的一个点连一条INF有向边（连一条即可，不必连所有）。

初始化完成后，在反向图（惯用链式前向星的表示，在跑最小割之前，边权为0的边就是反向图的边）上拓扑排序，删去在环中的点，留下有效点。

然后在建的这个图上跑最小割。

最终的答案为：源点到「与源点相连的所有有效点」的边权和减去网络最小割。

建模是个好能力，希望包括我在内的每一个OIer都能通过不懈努力获得。

加油。

#include <algorithm>

#include <climits>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int MAXN=10000,MAXM=900000;

bool exist[MAXN]/*拓扑排序有效点标记*/,vis[MAXN];

int n,m,N,S,T,cnt,ans,head[MAXN],cur[MAXN]/*当前弧*/,inn[MAXN]/*反图入度*/,dis[MAXN]/*层次图*/;

struct edge

{

	int nxt,to,w;

}e[MAXM];

void AddEdge(int x,int y,int w)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	e[cnt].w=w;

	head[x]=cnt;

}

void AddEdges(int x,int y,int w)

{

	AddEdge(x,y,w);

	AddEdge(y,x,0);

	++inn[x];//预处理反图入度

}

void T_Sort(int S)

{

	queue<int> q;//栈或队列都可以（优先队列或者手写堆其实也没问题）

	for(int i=S;i<=T;++i)

		if(!inn[i])

			q.push(i);//入度为0的入队

	while(!q.empty())

	{

		int x=q.front();

		q.pop();

		exist[x]=1;

		for(int i=head[x],t;i;i=e[i].nxt)

			if(!e[i].w && !--inn[t=e[i].to])

				q.push(t);

	}

	for(int i=head[S];i;i=e[i].nxt)

		if(!inn[e[i].to])

			ans+=e[i].w;//事先累加源点到「与源点相连的所有有效点」的边权

}

bool BFS(int S)

{

	queue<int> q;

	memset(dis,0,sizeof dis);

	memset(vis,0,sizeof vis);

	q.push(S);

	vis[S]=1;

	while(!q.empty())

	{

		int x=q.front();

		q.pop();

		for(int i=head[x],t;i;i=e[i].nxt)

			if(e[i].w && exist[t=e[i].to] && !vis[t])

			{

				vis[t]=1;

				dis[t]=dis[x]+1;

				q.push(t);

			}

		if(vis[T])//已经处理到汇点就退出

			return 1;

	}

	return 0;

}

int DFS(int x,int k)

{

	if(x==T)

		return k;

	int tmp=0;//这个累加必须有，否则最后一个点会被卡掉。

	for(int i=cur[x],t,f;i;i=e[i].nxt)

		if(e[i].w && exist[t=e[i].to] && dis[t]==dis[x]+1 && (f=DFS(t,min(k,e[i].w))))

		{

			cur[x]=i;

			e[i].w-=f;//当前边的边权

			e[((i-1)^1)+1].w+=f;//反向边的边权

			tmp+=f;

			k-=f;

		}

	if(!tmp)

		dis[x]=-1;//必须有的操作

	return tmp;

}

void Dinic(void)

{

	int f;

	while(BFS(S))//预处理层次图，直到无法间出层次图

		while(memcpy(cur,head,sizeof cur),f=DFS(S,INT_MAX))//跑DFS直到当前层次图上无法增广。

			ans-=f;//连接源点的边权和减去最小割

}

int main(int argc,char *argv[])

{

	scanf("%d %d",&n,&m);

	N=n*m,T=N+1;//N是总点数，T是汇点

	for(int i=1,w,k;i<=N;++i)

	{

		scanf("%d %d",&w,&k);

		if(i%m)//如果不是当前行最后一个点，就向右连一条边。

			AddEdges(i,i+1,INT_MAX);

		if(w>0)

			AddEdges(S,i,w);//连源点

		else if(w<0)

			AddEdges(i,T,-w);//连汇点

		for(int j=1,r,c;j<=k;++j)

		{

			scanf("%d %d",&r,&c);

			AddEdges(r*m+c+1,i,INT_MAX);//保护关系

		}

	}

	T_Sort(S);//拓扑排序

	Dinic();//最小割

	printf("%d",ans);

	return 0;

}

谢谢阅读。

巴特西

[Luogu 2805] NOI2009 植物大战僵尸

<题目链接>

最新文章

热门文章