首页 > 其他 > 详细

魔术球问题(网络流,二分图)

时间:2020-02-23 17:57:40      阅读:54      评论:0      收藏:0      [点我收藏+]

魔术球问题(luogu)

Description

题目描述

«问题描述:

假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,...的球。

(1)每次只能在某根柱子的最上面放球。

(2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在n根柱子上最多能放多少个球。例如,在4 根柱子上最多可放11 个球。

«编程任务:

对于给定的n,计算在n根柱子上最多能放多少个球。

输入格式

第1 行有1个正整数n,表示柱子数。

输出格式

程序运行结束时,将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。

接下来的n行,每行是一根柱子上的球的编号。

4<=n<=55

 

Solution

"依次放入编号为1,2,3,...的球"和同一柱子上先后放入的球之间的约束关系提示我们这与最小路径点覆盖有关。

从编号为 i 的球向可以放在它后面的球连一条有向边,

由于每个球都要放入,这道题变成了求最小路径点覆盖为 n 的点最多的图的点数

可以用二分图做(而且比网络流快qwq)

 

Code

 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
const int N=6010,M=5000001;
int head[N],ver[M],nxt[M],tot;
int n,ans=1,match[N],vis[N],cnt,pp,pre[N];
bool flag[N];
vector <int> an;
bool is(int x)
{
    int y=sqrt(x);
    return y*y==x;
}
bool dfs(int x)
{
    for(int i=head[x],y;i;i=nxt[i])
        if(vis[y=ver[i]]!=cnt)
        {
            vis[y]=cnt;
            if(!match[y] || dfs(match[y]))
            {
                match[y]=x,match[x]=y;
                return 1;
            }
        }
    return 0;
}
void add(int x,int y)
{
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int main()
{
    scanf("%d",&n);
    for(;;ans++)
    {
        cnt++;
        for(int i=ans+1;i<ans*2;i++)
            if(is(i)) add(ans,i-ans+3000);
        memcpy(pre,match,sizeof(pre));
        if(dfs(ans)) pp++;
        if(ans-pp>n) break;
    }
    printf("%d\n",ans-1);
    for(int i=ans-1;i>=1;i--)
        if(!flag[i])
        {
            int x=i;
            an.clear();
            while(x>0) an.push_back(x),flag[x]=true,x=pre[x]-3000;
            int size=an.size();
            for(int j=size-1;j>=0;j--)
                printf("%d ",an[j]);
            puts("");
        }
    return 0;
}

 

 

 

 

魔术球问题(网络流,二分图)

原文:https://www.cnblogs.com/hsez-cyx/p/12350724.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!