网络流24题——魔术球问题 luogu 2765

题目描述：这里

这道题是网络流问题中第一个难点，也是一个很重要的问题

如果直接建图感觉无从下手，因为如果不知道放几个球我就无法得知该如何建图（这是很显然的，比如我知道 $1+48=49=7^2$ ，可是我都不知道是否能放到第48个球，那我怎么知道如何建边呢？）

所以这时就体现出了一个很重要的想法：枚举答案！！！

我们知道，正常有二分答案的做法，可以二分一个答案然后检验

这里用类似的想法，但由于答案比较小而且建图更方便，所以我们直接从小往大枚举答案即可

之所以建图更方便，是因为如果我们从小向大枚举答案，那么原先建好的边是不用动的，因为原先的球一定要放，所以我们只需研究新来的球就可以了

而且还有一个好处，就是这样的话我们只需在残余网络上跑最大流，所以速度会更快一些？（口胡）

这里还有一个问题：如何建图？

直接从源点向新来的球连边，然后由新来的球向汇点连边，容量为1？

那这最大流不是要多少有多少的吗......

所以这样做显然不正确

正确的做法：把一个球拆成两个（设为x与y），然后由源点向x连边，容量为1，由y向汇点连边，容量为1,

接下来，我们找出所有满足与当前球编号和为完全平方数的球，将当前球的x点向那些球的y点连边，容量为1

然后每次在残余网络上跑最大流，如果最大流为0则说明需要新加一个柱子，加到柱子数超过给出的即结束

稍微解释一下这种做法的原因：我们把球拆成两个点以后，可以看做是一个球的上下两面，x表示与原先有的球相接，y表示在它上面放新的球的能力。

这样的话，我们把新来的x与原先合法的y相连后跑最大流，如果新的最大流不为0，说明这个新来的球能成功地放在一个原有的球上（这是因为最大流不为0说明了一条原来由某个y指向汇点的边本来流量是0，但现在流量变成了1而且保证了原有流量不变，这也就说明新来的球放在了一个柱上）

那么就自然是合法的了

然后是下一个问题（所以说这道题是好题，因为有很多个问题）

如何输出方案？

基于上面的解释，输出方案就变得简单了：我们从小往大枚举每个球，如果这个球还没被放在一个柱上则新开一个柱，然后顺着这个球的y点向下寻找，每找到一个没放下的点就放在这个柱上即可

可能说的有些抽象，具体解释一下：

我们从y点向外找边，是因为从y出发的边只要终点不是汇点那么一定是反向边！

如果反向边容量不为0，说明对应的正向边有1的流量，也就说明这个点之上被放上了一个点！

那么我们只需找出这个点，然后向下递归即可

注意找到一个点即可结束本层的寻找，因为一个球上最多只能放一个球啊

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

using namespace std;

const int inf=0x3f3f3f3f;

struct Edge

{

	int next;

	int to;

	int val;

}edge[2000005];

int head[10005];

bool used[10005];

int cur[10005];

int cnt=1;

int st,ed;

int n;

int dis[10005];

void init()

{

	memset(head,-1,sizeof(head));

	cnt=1;

}

void add(int l,int r,int w)

{

	edge[cnt].next=head[l];

	edge[cnt].to=r;

	edge[cnt].val=w;

	head[l]=cnt++;

}

int ide(int x)

{

	return (x&1)?x+1:x-1;

}

bool bfs()

{

	memcpy(cur,head,sizeof(head));

	memset(dis,0,sizeof(dis));

	queue <int> M;

	M.push(st);

	dis[st]=1;

	while(!M.empty())

	{

		int u=M.front();

		M.pop();

		for(int i=head[u];i!=-1;i=edge[i].next)

		{

			int to=edge[i].to;

			if(edge[i].val&&!dis[to])dis[to]=dis[u]+1,M.push(to);

		}

	}

	return dis[ed];

}

int dfs(int x,int lim)

{

	if(x==ed)return lim;

	int ret=0;

	for(int i=cur[x];i!=-1;i=edge[i].next)

	{

		int to=edge[i].to;

		if(edge[i].val&&dis[to]==dis[x]+1)

		{

			int temp=dfs(to,min(lim,edge[i].val));

			if(temp)

			{

				lim-=temp;

				ret+=temp;

				edge[i].val-=temp;

				edge[ide(i)].val+=temp;

				if(!lim)break;

			}

		}

		cur[x]=i;

	}

	return ret;

}

int dinic()

{

	int ret=0;

	while(bfs())ret+=dfs(st,inf);

	return ret;

}

void print(int x)

{

	used[x]=1;

	printf("%d ",x);

	for(int i=head[(x<<1)|1];i!=-1;i=edge[i].next)

	{

		int to=edge[i].to;

		if(!edge[i].val||used[to>>1]||to==ed)continue;

		print(to>>1);

		break;

	}

}

int main()

{

	scanf("%d",&n);

	init();

	int tot;

	st=0,ed=1;

	int s=0;

	for(tot=1;tot;tot++)

	{

		add(st,tot<<1,1);

		add(tot<<1,st,0);

		add((tot<<1)|1,ed,1);

		add(ed,(tot<<1)|1,0);

		for(int j=1;j*j<2*tot;j++)

		{

			if(j*j>tot)add(tot<<1,((j*j-tot)<<1)|1,1),add(((j*j-tot)<<1)|1,tot<<1,0);

		}

		if(!dinic())s++;

		if(s>n)break;

	}

	printf("%d\n",tot-1);

	for(int i=1;i<tot;i++)

	{

		if(used[i])continue;

		print(i);

		printf("\n");

	}

	return 0;

}

巴特西

网络流24题——魔术球问题 luogu 2765

最新文章

热门文章