【网络流24题】魔术球问题

以珠子为点，满足条件就两两连边

那么就是让你求n条路径最多能覆盖多少节点。

众所周知，最小边覆盖=点总数-最大匹配

不会看这里Link

于是拆点跑二分图即可

大概就是S向x连边

满足条件的点k向x'连边

x'向T连边

有两种方式

1.我们轮流加点，每次在残量网络跑最大流就可以了

2.我们二分答案，每次重新跑最大流

实测前一种更快。

QwQ

输出答案就看哪条边的流量跑满了。

/*
@Date    : 2019-07-20 15:12:45
@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 N=10000;
const int T=30000;
const int S=0;
int sqr[N+7];
struct edge{
	int v,nxt,flow;
}e[200007];
int head[50007],cnt;
int cur[50007];
inline void add(int u,int v,int flow)
{
	e[cnt]=(edge){v,head[u],flow};
	head[u]=cnt++;
}
inline void link(int u,int v,int flow){add(u,v,flow),add(v,u,0);}
int dep[50007];
inline bool bfs(void)
{
	static int Q[50007],l,r;
	memset(dep,0,sizeof dep);
	dep[Q[l=r=0]=S]=1;
	while(l<=r)
	{
		int p=Q[l++];
		for(int i=head[p];~i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(e[i].flow&&dep[v]==0)dep[v]=dep[p]+1,Q[++r]=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;~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(e[i].flow&&dep[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;
			if(restflow==0)break;
		}
	}
	return sumflow;
}
inline int dinic()
{
	int maxflow=0;
	while(bfs())
		memcpy(cur,head,sizeof head),maxflow+=dfs(S,2147483647);
	return maxflow;
}
int main(void)
{
	memset(head,-1,sizeof head);
	int n=gi;
	for(int i=1;i<=N;++i)sqr[i]=i*i;
	int num=1,sum=0;
	while(1)
	{
		int maxsqr=lower_bound(sqr+1,sqr+N+1,2*num)-sqr-1;
		int minsqr=upper_bound(sqr+1,sqr+N+1,num)-sqr;
		link(S,num,1),link(num+N,T,1);	
		for(int i=maxsqr;i>=minsqr;--i)link(sqr[i]-num,num+N,1);
		sum+=dinic();
		if(num-sum>n)break;
		++num;
	}
	--num;
	pi(num,'
');
	static int to[50007];
	for(int k=1;k<=num;++k)
		for(int i=head[k];~i;i=e[i].nxt)
			if(!e[i].flow){if(e[i].v>N)to[k]=e[i].v-N;break;}
	static int vis[50007];
	for(int i=1;i<=num;i++)
		if(!vis[i])
		{
			for(int k=i;k;k=to[k])vis[k]=1,pi(k,' ');
			putchar('
');
		}
	return 0;
}