网络流24题- 魔术球问题
魔术球问题链接
Description
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可
放11 个球。
编程任务：
对于给定的n，计算在n根柱子上最多能放多少个球。
Input
4
Output
11
1 8
2 7 9
3 6 10
4 5 11
我们把x, y 满足(x < y && x + y是完全平方数)连一条边，我们要用尽量少的柱子放尽可能多的边。即用最少的路径覆盖尽可能多的点。问题就转化成了求有向图的最小路径覆盖。那么我们要求的就是如果1~n的数进行连边，求得的最小路径覆盖大于我们的柱子数。那么我们的答案就是对1~n-1的点求最小路径覆盖。并求出最小路径覆盖的路径
首先是一发及其暴力的枚举dinic，打个表，提前算出55个答案是在数字几的dinic的图中得出了，这个代码暴力TLE但是如果打出了表那么复杂度就是一次dinic的
#include <bits/stdc++.h>
using namespace std;
int k;
struct Dinic {
static const int MAXN = 30005 + 7;
static const int MAXM = 1e7 + 7;
static const int INF = 0x3f3f3f3f;
int n, m, s, t;
int first[MAXN], cur[MAXN], dist[MAXN], sign;
struct Node {
int to, flow, next;
} edge[MAXM];
inline void init(int start, int vertex, int ss, int tt) {
n = vertex, s = ss, t = tt;
for(int i = start; i <= n; i++ ) {
first[i] = -1;
}
sign = 0;
}
inline void addEdge(int u, int v, int flow) {
edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
first[u] = sign++;
}
inline void add_edge(int u, int v, int flow) {
addEdge(u, v, flow);
addEdge(v, u, 0);
}
int match[MAXN] = {0}, vis[MAXN] = {0};
void show_graph() {
for(int i = 1; i <= k; i++ ) {
for(int j = first[i]; ~j; j = edge[j].next) {
int to = edge[j].to, w = edge[j].flow;
if(to != s && edge[j ^ 1].flow) {
//printf("%d ", to - k);
match[i] = to - k;
}
}
}
// for(int i = 1; i <= k; i++ ) {
// printf("[%d %d]
", i, match[i]);
// }
for(int i = 1; i <= k; i++ ) {
int now = i;
if(vis[i]) {
continue;
}
while(1) {
printf("%d", now);
vis[now] = 1;
now = match[now];
if(now == 0) {
puts("");
break;
} else {
printf(" ");
}
}
}
}
inline int dinic() {
int max_flow = 0;
while(bfs(s, t)) {
for(int i = 0; i <= n; i++ ) {
cur[i] = first[i];
}
max_flow += dfs(s, INF);
}
return max_flow;
}
bool bfs(int s, int t) {
memset(dist, -1, sizeof(dist));
queue<int>que;
que.push(s), dist[s] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
if(now == t) {
return 1;
}
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == -1 && flow > 0) {
dist[to] = dist[now] + 1;
que.push(to);
}
}
}
return 0;
}
int dfs(int now, int max_flow) {
if(now == t) {
return max_flow;
}
int ans = 0, next_flow = 0;
for(int &i = cur[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == dist[now] + 1 && flow > 0) {
next_flow = dfs(to, min(max_flow - ans, flow));
ans += next_flow;
edge[i].flow -= next_flow;
edge[i ^ 1].flow += next_flow;
if(ans == max_flow) {
return max_flow;
}
}
}
if(ans == 0) {
return dist[now] = 0;
}
return ans;
}
} cwl;
int main() {
int n;
scanf("%d", &n);
for(k = 1; k; k++ ) {
cwl.init(0, 2 * k + 1, 0, 2 * k + 1);
for(int i = 1; i <= k; i++ ) {
cwl.add_edge(0, i, 1);
cwl.add_edge(i + k, 2 * k + 1, 1);
}
for(int i = 1; i <= k; i++ ) {
for(int j = i + 1; j <= k; j++ ) {
int val = i + j;
int sqr = sqrt(val);
if(sqr * sqr == val) {
cwl.add_edge(i, j + k, 1);
}
}
}
int ans = cwl.dinic();
if(k - ans > n) {
printf("%d
", k - 1);
k--;
cwl.init(0, 2 * k + 1, 0, 2 * k + 1);
for(int i = 1; i <= k; i++ ) {
cwl.add_edge(0, i, 1);
cwl.add_edge(i + k, 2 * k + 1, 1);
}
for(int i = 1; i <= k; i++ ) {
for(int j = i + 1; j <= k; j++ ) {
int val = i + j;
int sqr = (int)sqrt(val);
if(sqr * sqr == val) {
cwl.add_edge(i, j + k, 1);
}
}
}
ans = cwl.dinic();
cwl.show_graph();
break;
}
}
return 0;
}
然后是用打的表之间知道答案一次dinic求答案，24MS。
#include <bits/stdc++.h>
using namespace std;
int k;
int ans[] = {0, 1,3,7,11,17,23,31,39,49,59,71,83,97,111,127,143,161,179,199,219,241,263,287,311,337,363,391,419,449,479,511,543,577,611,647,683,721,759,799,839,881,923,967,1011,1057,1103,1151,1199,1249,1299,1351,1403,1457,1511,1567};
struct Dinic {
static const int MAXN = 30005 + 7;
static const int MAXM = 1e7 + 7;
static const int INF = 0x3f3f3f3f;
int n, m, s, t;
int first[MAXN], cur[MAXN], dist[MAXN], sign;
struct Node {
int to, flow, next;
} edge[MAXM];
inline void init(int start, int vertex, int ss, int tt) {
n = vertex, s = ss, t = tt;
for(int i = start; i <= n; i++ ) {
first[i] = -1;
}
sign = 0;
}
inline void addEdge(int u, int v, int flow) {
edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
first[u] = sign++;
}
inline void add_edge(int u, int v, int flow) {
addEdge(u, v, flow);
addEdge(v, u, 0);
}
int match[MAXN] = {0}, vis[MAXN] = {0};
void show_graph() {
for(int i = 1; i <= k; i++ ) {
for(int j = first[i]; ~j; j = edge[j].next) {
int to = edge[j].to, w = edge[j].flow;
if(to != s && edge[j ^ 1].flow) {
//printf("%d ", to - k);
match[i] = to - k;
}
}
}
// for(int i = 1; i <= k; i++ ) {
// printf("[%d %d]
", i, match[i]);
// }
for(int i = 1; i <= k; i++ ) {
int now = i;
if(vis[i]) {
continue;
}
while(1) {
printf("%d", now);
vis[now] = 1;
now = match[now];
if(now == 0) {
puts("");
break;
} else {
printf(" ");
}
}
}
}
inline int dinic() {
int max_flow = 0;
while(bfs(s, t)) {
for(int i = 0; i <= n; i++ ) {
cur[i] = first[i];
}
max_flow += dfs(s, INF);
}
return max_flow;
}
bool bfs(int s, int t) {
memset(dist, -1, sizeof(dist));
queue<int>que;
que.push(s), dist[s] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
if(now == t) {
return 1;
}
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == -1 && flow > 0) {
dist[to] = dist[now] + 1;
que.push(to);
}
}
}
return 0;
}
int dfs(int now, int max_flow) {
if(now == t) {
return max_flow;
}
int ans = 0, next_flow = 0;
for(int &i = cur[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == dist[now] + 1 && flow > 0) {
next_flow = dfs(to, min(max_flow - ans, flow));
ans += next_flow;
edge[i].flow -= next_flow;
edge[i ^ 1].flow += next_flow;
if(ans == max_flow) {
return max_flow;
}
}
}
if(ans == 0) {
return dist[now] = 0;
}
return ans;
}
} cwl;
int get_value(int n) {
printf("%d
", n);
k = n;
cwl.init(0, 2 * k + 1, 0, 2 * k + 1);
for(int i = 1; i <= k; i++ ) {
cwl.add_edge(0, i, 1);
cwl.add_edge(i + k, 2 * k + 1, 1);
}
for(int i = 1; i <= k; i++ ) {
for(int j = i + 1; j <= k; j++ ) {
int val = i + j;
int sqr = sqrt(val);
if(sqr * sqr == val) {
cwl.add_edge(i, j + k, 1);
}
}
}
int ans = cwl.dinic();
cwl.show_graph();
}
int main() {
int n;
scanf("%d", &n);
get_value(ans[n]);
return 0;
}