【网络流-最大流】魔术球
程序员文章站
2022-06-10 21:20:17
...
链接
https://www.luogu.org/problemnew/show/P2765
大意
有个球,要把它们放在任意数量的桌子上,且必须满足相邻两球的和是完全平方数,否则必须新开一张桌子,问最少要几张桌子
思路
本来这题是一个贪心水题,但因为老师要求用网络流做,就打了一个网络流
具体的思路是如果两个数的和是完全平方数,则将它们连边,最后求一遍最大流就行了
然后因为学校题库没有spj所以WA了,但在洛谷能A
代码
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 100001
using namespace std;
struct node{int to,next,v;}e[N];
int l[N],n,S,T,d[N],tot,ans,nex[N],w[N];char c;
bool vis[N];
void add(int u,int v,int w)
{
e[tot].to=v;e[tot].next=l[u];e[tot].v=w;l[u]=tot++;
e[tot].to=u;e[tot].next=l[v];e[tot].v=0;l[v]=tot++;
return;
}
void write(int x){if(x>9)write(x/10);putchar(x%10+48);return;}
void writes(int x){write(x);putchar(32);return;}
void writeln(int x){write(x);putchar(10);return;}
bool bfs()
{
memset(d,-1,sizeof(d));
queue<int>q;q.push(S);d[S]=0;
while(q.size())
{
int x=q.front();q.pop();
for(int i=l[x];i!=-1;i=e[i].next)
{
int y=e[i].to;
if(e[i].v&&d[y]==-1)
{
d[y]=d[x]+1;
q.push(y);
}
}
}
return d[T]!=-1;
}
int dfs(int x,int flow)
{
if(x==T) return flow;
int rest=0,k;
for(int i=l[x];i!=-1;i=e[i].next)
{
int y=e[i].to;
if(e[i].v&&d[x]+1==d[y])
{
k=dfs(y,min(flow-rest,e[i].v));
if(k) nex[x>>1]=y>>1;
e[i].v-=k;rest+=k;e[i^1].v+=k;
}
}
if(!rest) d[x]=-1;
return rest;
}
int dinic()
{
int r=0,t=0;
while(bfs()) while(t=dfs(S,1e9)) r+=t;
return r;
}
int main()
{
memset(l,-1,sizeof(l));//这一行非常非常重要!
memset(nex,-1,sizeof(nex));
scanf("%d",&n);S=0;T=10010;
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);
if(!dinic())w[++now]=num;
}
writeln(--num);
int k;
for(int i=1;i<=n;i++)
if(!vis[w[i]])
{
k=w[i];
writes(k);vis[k]=true;
while(nex[k]>0&&nex[k]!=T>>1)
k=nex[k],vis[k]=true,writes(k);
putchar(10);
}
}
上一篇: 颈椎疼痛 午休时间做这事能缓解
下一篇: 午饭后做好七件事,,让身体更健康