P2765 魔术球问题

Posted on | In

题目链接

题目描述

问题描述：

假设有n$(4 <= n <= 55)$根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。

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

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

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

编程任务：

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例：

4

输出样例：

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

Solution

此题据说贪心可做，但因为属于网络流24题，所以还是用网络流来做了(才不是不会贪心做法呢)。
洛谷的题解很Nice了，就不抄一遍了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;

// -------------------------head start here---------------------------------------
#define pb      push_back
#define eb		emplace_back
#define sz(a) 	(int)a.size()
#define endl    "\n"
#define all(a)  a.begin(),a.end()
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define drep(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Rep(i, a, b) for(int i = int(a); i <= int(b); i++)
#define dRep(i, a, b) for (int i = int(a); i >= int(b); i--)
#define mst(a, x) memset(a, x, sizeof a)

#ifdef Semon0x29a
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 0
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using VI = vector<int>;
using VL = vector<long long>;

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int Move[][3] = { { 0, 0 },{ 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 },{ 1, 1 },{ 1, -1 },{ -1, 1 },{ -1, -1 } };

template <class T> inline T sqr(T x) { return x * x; }
ll qpow(ll a, ll t) { a %= MOD; ll b = 1; for (; t; t >>= 1, (a *= a) %= MOD) if (t & 1) (b *= a) %= MOD; return b; }
template <class T> inline bool chkmax(T& a, T b) { return (a < b) ? (a = b, 1) : 0; }
template <class T> inline bool chkmin(T& a, T b) { return (a > b) ? (a = b, 1) : 0; }
// -----------------------------head end here-------------------------------------
// -------------------------------------------------------------------------------

struct edge {
    int v, w, next;
    edge(int vv = 0, int ww = 0, int nxt = -1) : v(vv), w(ww), next(nxt) {}
}G[maxn];

int tot, head[maxn], level[maxn], cur[maxn], go[maxn];

void init() {
    tot = 0;
    mst(head, -1), mst(go, -1);
}

void addedge(int u, int v, int w) {
    G[tot] = edge(v, w, head[u]); head[u] = tot++;
    G[tot] = edge(u, 0, head[v]); head[v] = tot++;
}

bool bfs() {
    mst(level, 0);
    queue<int> Q;
    Q.push(0); level[0] = 1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; i != -1; i = G[i].next) {
            edge& e = G[i];
            if (level[e.v] == 0 && e.w > 0) {
                level[e.v] = level[u] + 1;
                Q.push(e.v);
            }
        }
    }
    return level[maxn - 1] != 0;
}

int dfs(int u, int flow) {
    if (u == maxn - 1) return flow;
    int change = 0;
    for (int &i = cur[u]; flow > 0 && i != -1; i = G[i].next) {
        edge& e = G[i];
        if (level[e.v] == level[u] + 1 && e.w > 0) {
            int tmp = dfs(e.v, min(flow, e.w));
            if (tmp == 0) continue;
            if (e.v != maxn - 1) go[u >> 1] = e.v >> 1;
            e.w -= tmp, G[i ^ 1].w += tmp;
            flow -= tmp, change += tmp;
        }
    }
    return change;
}

int Dinic() {
    int res = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof head);
        res += dfs(0, INF);
    }
    return res;
}

int32_t main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; 
    while (cin >> n) {
        init();

        int rt = 0, now = 0, in[105] = { 0 };
        while (rt <= n) {
            ++now; addedge(0, now << 1, 1), addedge(now << 1 | 1, maxn - 1, 1);
            for (int i = (int)sqrt(now) + 1; i * i < now * 2; i++) {
                addedge((i * i - now) << 1, now << 1 | 1, 1);
            }
            int tmp = Dinic();
            if (tmp == 0) in[++rt] = now;
        }

        bool vis[maxn] = { 0 };
        cout << now - 1 << endl;
        Rep(i, 1, n) {
            if (vis[in[i]]) continue;
            for (int st = in[i]; st != -1; vis[st] = 1, st = go[st]) {
                cout << st << " \n"[go[st] == -1];
            }
        }
    }
}