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

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

内存限制:256 MiB时间限制:1000 ms标准输入输出
题目类型:传统评测方式:Special Judge
上传者: 匿名

题目描述

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

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

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

输入格式

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

输出格式

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

样例

样例输入

4

样例输出

11
1 8
2 7 9
3 6 10
4 5 11

数据范围与提示

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");
}
}

点不重复最短路径覆盖

上一篇:[转]Linux进程间通信——使用信号


下一篇:Luogu 2764 最小路径覆盖问题 / Libre 6002 「网络流 24 题」最小路径覆盖 (网络流,最大流)