LibreOJ 6003. 「网络流 24 题」魔术球贪心或者最小路径覆盖

2022-11-01 22:02:05

6003. 「网络流 24 题」魔术球

内存限制：256 MiB时间限制：1000 ms标准输入输出

题目类型：传统评测方式：Special Judge

上传者：匿名

提交提交记录统计讨论测试数据

题目描述

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

每次只能在某根柱子的最上面放球。
在同一根柱子中，任何 2 22 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 n nn 根柱子上最多能放多少个球。

输入格式

文件第 1 11 行有 1 11 个正整数 n nn，表示柱子数。

输出格式

第一行是球数。接下来的 n nn 行，每行是一根柱子上的球的编号。

样例

样例输入

样例输出

数据范围与提示

1≤n≤55 1 \leq n \leq 551≤n≤55

题目链接：https://loj.ac/problem/6003

题意：中文题目，意思明显。

思路：贪心或者点不重复的最小路径覆盖。现在讲一下我的艰难的ac历程，好吧，其实还是蛮简单的。我首先暴力二分ans，然后求最小路径覆盖是否为n，发现TLE，此时我发现了一个问题，那就是n很小，于是我就把每个n的ans打了个表出来，然后直接跑匹配求最短路，AC了。尽管AC了，然后我发现了，这其实是一个贪心题。按照如下的顺序放球：

1 3 6 10 15....

2 7 9 16 20....

4 5 11 14 22....

8 7 23....

12 13....

....

现在想一下，其实不用打表，直接用匹配跑最短路。将答案从1依次递增，然后每次跑匹配，但是每次跑的时候不需要初始化，也不要从1开始，直接从i开始，因为前面的已经跑过了，并且没有新增加前面的点出度的边，所以可以直接从i开始。最后当最短路径大于n是退出循环就可以了。

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<queue>

#include<stack>

#include<map>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int maxn=1e6+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;

const ll INF=1e18+;

vector<ll>G[maxn];

bool used[maxn];

int cx[maxn],cy[maxn];

bool vis[maxn];

int res=;

bool dfs(int u)

{

    for(int i=; i<G[u].size(); i++)

    {

        int v=G[u][i];

        if(used[v]) continue;

        used[v]=true;

        if(cy[v]<||dfs(cy[v]))

        {

            cx[u]=v,cy[v]=u;

            return true;

        }

    }

    return false;

}

int solve(int n)

{

    res+=dfs(n);

    return res;

}

int main()

{

    int n;

    scanf("%d",&n);

    int ans=;

    memset(cx,-,sizeof(cx));

    memset(cy,-,sizeof(cy));

    for(int i=; i<=; i++)

    {

        int x=(int)(sqrt(i+));

        while(x*x-i<i)

        {

            if(x*x-i>=) G[i].push_back(x*x-i);

            x++;

        }

        if(i-solve(i)>n) break;

        ans=i;

    }

    memset(vis,false,sizeof(vis));

    printf("%d\n",ans);

    for(int i=ans; i>=; i--)

    {

        if(vis[i]) continue;

        printf("%d",i);

        for(int j=i; cx[j]!=-; j=cx[j],vis[j]=true)

            printf(" %d",cx[j]);

        printf("\n");

    }

}

点不重复最短路径覆盖

码农公寓