题解 P2765 【魔术球问题】

###这道题是一个非常好网络流题目 弱弱的说一句这是道题好像是网络流二十四题中的04 虽然可以用贪心或者一些玄学算法可以很快的跑过，但建议还是用网络流 并且网络流的建图真的很棒 **思路：** 我们先枚举球，一个个加到图里 #并在加边的过程是三个操作： - 当然不可缺少的是拆点把一个球x拆成x和x' - 下一步x连源点，x'连汇点都是容量为一的有向边 - 第三步是找这个数可以与那个数组成完全平方数，假设这个数为y，则y向x'连边 下面就是跑最大流了，在跑最大流的时候记录一下这个点向那个点流出流量（这就是代码中的nex[]） ) **\_最后就是最让人期待的上代码环节了 ┗|｀O′|┛ 嗷~~\_** ```cpp #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发一下二分图的做法