题解 P2765 【魔术球问题】
这道题是一个非常好网络流题目
弱弱的说一句这是道题好像是网络流二十四题中的04
虽然可以用贪心或者一些玄学算法可以很快的跑过，但建议还是用网络流
并且网络流的建图真的很棒
思路：
我们先枚举球，一个个加到图里
并在加边的过程是三个操作：
-
当然不可缺少的是拆点把一个球x拆成x和x'
-
下一步x连源点，x'连汇点都是容量为一的有向边
-
第三步是找这个数可以与那个数组成完全平方数，假设这个数为y，则y向x'连边
下面就是跑最大流了，在跑最大流的时候记录一下这个点向那个点流出流量（这就是代码中的nex[]）
_最后就是最让人期待的上代码环节了 ┗|｀O′|┛ 嗷~~_
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int INF=(1<<30);
const int maxn=400000;
int idx=0,e[maxn],f[maxn],ne[maxn],h[100000];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}
int S,T,ch[maxn],q[maxn],nex[maxn];
bool tell(){
memset(ch,-1,sizeof(ch));
int head=0,tail=0;
ch[q[0]=S]=0;
while(head<=tail){
int t=q[head++];
for(int i=h[t];i!=-1;i=ne[i]){
if(ch[e[i]]==-1&&f[i]){
ch[q[++tail]=e[i]]=ch[t]+1;
}
}
}
return ch[T]!=-1;
}
int zeng(int a,int b){
if(a==T)return b;
int r=0;
for(int i=h[a];i!=-1;i=ne[i]){
if(ch[a]+1==ch[e[i]]&&f[i]){
int t=zeng(e[i],min(b-r,f[i]));
if(t>0)nex[a>>1]=(e[i]>>1);
f[i]-=t;r+=t;f[i^1]+=t;
}
}
if(!r)ch[a]=-1;
return r;
}
int dinic(){
int r=0,t=0;
while(tell()){
while(t=zeng(S,INF)){
r+=t;
}
}
return r;
}
bool vis[maxn];
int w[1000];
int main(){
int n;
S=0;T=10010;
memset(h,-1,sizeof(h));
memset(nex,-1,sizeof(nex));
scanf("%d",&n);
int now=0,num=0;
while(now<=n){
++num;
add(S,num<<1,1);add((num<<1)|1,T,1);
for(int i=sqrt(num)+1;i*i<(num<<1);i++)add((i*i-num)<<1,(num<<1)|1,1);
int s=dinic();
if(s==0)w[++now]=num;
}
printf("%d\n",--num);
memset(vis,false,sizeof(vis));
int k;
for(int i=1;i<=n;i++){
if(!vis[w[i]]){
k=w[i];printf("%d ",k);vis[w[i]]=true;
while(nex[k]!=-1&&nex[k]!=(T)>>1&&nex[k]!=0){
k=nex[k];
vis[k]=true;
printf("%d ",k);
}
printf("\n");
}
}
}此题也可以用二分图做，希望能有dalao发一下二分图的做法