魔术球[网络流]

魔术球[网络流]

​​传送门​​

将和为平方数的两个数连边 , 从小到大枚举数 , 每次插入一个数就新加边

加了过后跑一遍网络流 , 如果发现流为0 , 那么这个数只能新作为一个开头

否则 , 我们就可以将它排在后面 , 然后个数 -= 最大流[想一想]

我们发现个数大于n时 , 枚举到的now-1就是答案

#include#define N 5005#define M 500050#define inf 0x3fffffffusing namespace std;int first[M],next[M],to[M],w[M],tot=1,cnt;int dis[M],n,st,ed,Is[N*N],vis[M],ans[M];void add(int x,int y,int z){ next[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;}bool bfs(){ queue q; memset(dis,-1,sizeof(dis)); q.push(st); dis[st]=0; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=first[x];i;i=next[i]){ int t=to[i]; if(dis[t]==-1 && w[i]){ dis[t] = dis[x] + 1; if(t==ed) return true; q.push(t); } } }return false;}int dfs(int u,int flow){ int ans=0; if(u==ed) return flow; for(int i=first[u];i;i=next[i]){ int t=to[i]; if(dis[t] == dis[u]+1){ int delta = dfs(t,min(flow , w[i])); ans += delta , flow -= delta; w[i] -= delta , w[i^1] += delta; if(flow <= 0) break; } }if(flow) dis[u] = -1; return ans;} void Printf(int u){ if(vis[u]) return; printf("%d ",u); vis[u]=1; for(int i=first[u];i;i=next[i]){ int t=to[i]; if(!w[i] && t>N) Printf(t-N); }}int Dinic(){ int ans=0; while(bfs()){ if(int x=dfs(st,inf)) ans += x; }return ans;}int main(){ scanf("%d",&n); for(int i=1;i<=5000;i++) Is[i*i]=1; st=0 , ed=N+N; for(int now=1,tmp=1;;tmp++,now++){ add(st,now,1) , add(now,st,0); add(now+N,ed,1) , add(ed,now+N,0); for(int i=1;in){ printf("%d\n",now-1); for(int i=1;i<=cnt-1;i++) Printf(ans[i]) , printf("\n"); return 0; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。