例2：NC213818 [网络流24题]魔术球问题
题目：
• 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
编程任务：对于给定的n，计算在n根柱子上最多能放多少个球。
• 1≤n≤55
题解：
首先思想很重要，不是明显的图论，要往图论方向靠
建图方式：
S与左图所有数相连，右图所有数与T相连
对于一个进来的编号的球x，有两个选择：
第一个选择是放在某个和他能组成平方数的球（我们起名为y）的后面
第二个选择是自己单独出来成为开头
对于第一种选择，当然要y和x连一个边
对于第二种选择，S要和x连一个边
当然我们也要让x与T连一个边
但是一个点怎么能同时连多个，显然一个点是不够用的
我们将一个点给分开，分为x和x'
x与s相连，x'与t相连
为了满足第一种情况，对于满足条件的x和y两个点，连接y和x'
这样组成的图直接跑最大流算法即可
球和柱子同时加，跑出的最大流为省掉的柱子数，如果加入一个数当前最大流没有变化，说明柱子数+1，如果最大流+1，说明可以省下一个柱子、
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<queue>
#define in(x) scanf("%d",&x)
using namespace std;
const int maxn=1e5;
int n,all=0,num=0,nxt[maxn],to[maxn],head[maxn],d[maxn];
int w[maxn],cnt=1,s=0,t=50003,re[maxn],xia[maxn],vis[maxn];
queue<int>q;
void add(int x,int y,int we)
{
nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=we;
nxt[++cnt]=head[y];head[y]=cnt;to[cnt]=x;w[cnt]=0;
}
int bfs()
{
while(q.size()) q.pop();q.push(s);
memset(d,0,sizeof(d));d[s]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i])
{
int u=to[i];
if(d[u]||w[i]<=0) continue;
d[u]=d[x]+1;
q.push(u);
}
}
return d[t];
}
int dfs(int x,int flow)
{
if(x==t) return flow;
int k;
for(int i=head[x];i;i=nxt[i])
{
int u=to[i];
if(d[u]!=d[x]+1||w[i]<=0) continue;
if(k=dfs(u,min(w[i],flow)))
{
w[i]-=k;
w[i^1]+=k;
if(u!=t) xia[x>>1]=u>>1;
return k;
}
}
return 0;
}
int dinic()
{
int k=0;
while(bfs())
{
while(1)
{
int p=dfs(s,1e9);
if(!p) break;
k+=p;
}
}
return k;
}
int main()
{
in(n);
while(all<=n)
{
num++;
add(s,num<<1,1);
add((num<<1)|1,t,1);
for(int i=sqrt(num)+1;i*i<2*num;++i)//能组成平方数的数建边
add((i*i-num)<<1,(num<<1)|1,1);
int k=dinic();//k=1说明可以连在其他数后面，不用单独再用一个柱子
if(!k) re[++all]=num;
}
printf("%d\n",--num);
for(int i=1;i<=n;++i)
{
if(vis[re[i]]) continue;
int x=re[i];
vis[x]=1;
while(x!=0)
{
printf("%d ",x);
x=xia[x];
vis[x]=1;
}
printf("\n");
}
return 0;
}方法2：
匈牙利算法也可以做
给定了柱子数n（最小路径覆盖数）以及放球条件（建边条件），求最多有多少个球（最多有多少个点可以满足这个最小路径覆盖数）。
枚举球的数量。
每来一个球（点）m，枚举1..m-1的每个点i，若i+m满足建边条件（和为完全平方数）则按以下方式建边——
套路拆点，每个点i拆成Xi、Yi，对于一组i、m，连Xi<->Y(m+5000)双向，跑匈牙利算出最大匹配。
根据二分图相关定理：最小路径覆盖数=点数-最大匹配数。
算出当前图的最小路径覆盖k，与给定柱子数比较。
k<n，继续加球。
k=n，可能还有更大的答案，继续加球。
k>n，m-1就是答案，停止加球。
输出路径，遍历1..m-1每个X部点，向其匹配点走，直到无路可走，沿路标记为已遍历。
已遍历过的X部点不再遍历。
代码：
#include<bits/stdc++.h>
#define mem(x) memset(x,0,sizeof(x));
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
int n,m=0;
const int MAXP=5e3;
const int maxn=200009;
struct node{
int next,to;
}edge[maxn];
int cnt=0;
int head[maxn];
void add(int u,int v)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
bool iff(int x)
{
double t;
t=sqrt(x);
return (t==int(t));
}
int vis[maxn];
int match[maxn];
bool maxmatch(int u)
{
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
vis[v]=1;
if(match[v]==0||maxmatch(match[v]))
{
match[v]=u;
match[u]=v;
return 1;
}
}
}
return 0;
}
void Print(int x)
{
x+=MAXP;
do
{
x=x-MAXP;
cout<<x<<" ";
vis[x]=1;
x=match[x];
}while(x!=0);
cout<<endl;
}
int main()
{
cin>>n;
int ans=0;
do
{
m++;
int t=m+MAXP;
for(int i=1;i<m;i++)
{
if(iff(i+m))
{
add(i,t);
add(t,i);
}
}
mem(vis);
ans+=maxmatch(t);//ans为剩下的柱子，m为原本要花的柱子，m-ans为现在所需要的柱子
}while(m-ans<=n);
m--;
cout<<m<<endl;
mem(vis);
for(int i=1;i<=m;i++)
{
if(vis[i]==0)Print(i);
}
return 0;
} 
京公网安备 11010502036488号