思路:最小路径覆盖
这题就是把1到x分成若干组,每组内部满足限制,组内满足的限制可以用路径来限制,即每个点向能走到的点连边
尽可能覆盖更到的点转化为要把所有点覆盖并且分的组最少,就是最小路径覆盖
c ++代码
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 10010, M = 1000010, INF = 0x3f3f3f3f;
int h[N], e[M], f[M], ne[M], idx;
int d[N], cur[M], q[N];
bool st[N];
int n, S, T;
vector<int> ans[N];
int cnt;
bool is_square(int x)
{
int a = sqrt(x);
if(a * a == x) return true;
else return false;
}
void insert(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs()
{
memset(d, -1, sizeof(d));
int hh = 0, tt = 0;
q[0] = S, d[S] = 0, cur[S] = h[S];
while(hh <= tt){
int t = q[hh ++];
for(int i = h[t]; ~i; i = ne[i]){
int ver = e[i];
if(d[ver] == -1 && f[i]){
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
q[++ tt] = ver;
}
}
}
return false;
}
int dfs(int u, int limit)
{
if(u == T) return limit;
int flow = 0;
for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
cur[u] = i;
int ver = e[i];
if(d[ver] == d[u] + 1 && f[i]){
int t = dfs(ver, min(f[i], limit - flow));
if(!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int res = 0, flow;
while(bfs()) while(flow = dfs(S, INF)) res += flow;
return res;
}
int dfs(int u)
{
if(u & 1) u --;
ans[cnt].push_back(u >> 1);
st[u] = true;
for(int i = h[u]; ~i; i = ne[i]){
int ver = e[i];
if(!ver) continue;
if(ver & 1) ver --;
if(!f[i]) dfs(ver);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
S = 0, T = 1;
memset(h, -1, sizeof(h));
int sum = 0, num = 0;
while(1){
sum ++, num ++;
insert(S, num * 2, 1);
insert(num * 2 + 1, T, 1);
for(int i = 1; i < num; i ++)
if(is_square(i + num)) insert(i * 2, num * 2 + 1, 1);
sum -= dinic();
if(sum > n) break;
}
num --;
cout << num << endl;
for(int i = 2; i <= num * 2; i += 2)
if(!st[i]) dfs(i), cnt ++;
for(int i = 0; i < cnt; i ++){
for(auto c : ans[i])
cout << c << ' ';
cout << endl;
}
return 0;
}