网络流24题（05）魔术球问题（最小路径覆盖 + 最大流）

思路：

1. 要求相邻的 2 个球数字相加为完全平方数，则相当于从 1 开始构造出来一个有向无环图：1->3->6..

2. 模型就变成了“最小路径覆盖”的问题，找图中最少的路径数，这里的路径数就是题目的柱子数。继而建模成了“二分图匹配”求最大流的问题;

3. 因为对于数字的未知性，本题采取了枚举的方法，不过每次都是在上一次最大流的基础上继续增广;

4. 代码中需要用到一个很强的剪纸：在红色部分。正常 dinic 求最大流是不需要这句话的，因为增广的时候是允许流“撤销”的，但是本题

   不需要流撤销自己的错误也能达到正确的结果，仔细想想可能是因为这个有向图的原因，公共节点把图分隔开，始终都是一样的;

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 4010;
const int OFFSET = 2000;
const int INFS = 0x3FFFFFFF;

struct edge {
    int from, to, cap, flow;
    edge(int _from, int _to, int _cap, int _flow)
        : from(_from), to(_to), cap(_cap), flow(_flow) {}
};

class Dinic {
public:
    void addedge(int u, int v, int cap) {
        edges.push_back(edge(u, v, cap, 0));
        edges.push_back(edge(v, u, 0, 0));
        int m = edges.size();
        G[u].push_back(m - 2);
        G[v].push_back(m - 1);
    }
    bool BFS() {
        memset(vis, false, sizeof(vis));
        memset(d, 0, sizeof(d));

        queue<int> Q;
        Q.push(s);
        vis[s] = true;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow && e.cap > 0) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x, int aug) {
        if (x == t || aug == 0) return aug;
        int flow = 0;
        for (int i = 0; i < G[x].size(); i++) {
            edge& e = edges[G[x][i]];
            if (d[e.to] == d[x] + 1) {
                int f = DFS(e.to, min(aug, e.cap-e.flow));
                if (f == 0) continue;
                e.flow += f;
                edges[G[x][i]^1].flow -= f;
                flow += f;
                aug -= f;
                if (aug == 0) break;
            }
        }
        return flow;
    }
    int maxflow(int s, int t) {
        this->s = s, this->t = t;
        int flow = 0;
        while (BFS()) {
            flow += DFS(s, INFS);
        }
        return flow;
    }
    void cleardata(int n) {
        this->n = n;
        edges.clear();
        for (int i = 0; i < n; i++)
            G[i].clear();
    }
    void print(int x) {
        vis[x] = true;
        for (int i = 0; i < G[x].size(); i++) {
            edge& e = edges[G[x][i]];
            if (!vis[e.to] && e.flow == 1 && e.to != t) {
                printf(" %d", e.to - OFFSET); print(e.to - OFFSET);
                break;
            }
        }

    }
    void printpath(int num) {
        memset(vis, false, sizeof(vis));
        for (int x = 1; x <= num; x++) {
            if (!vis[x]) { 
                printf("%d", x); print(x); printf("\n");
            }
        }
    }
private:
    vector<edge> edges;
    vector<int> G[MAXN];
    int d[MAXN], s, t, n;
    bool vis[MAXN];
};

Dinic dc;
bool issquare[MAXN];

void initdata() {
    memset(issquare, false, sizeof(issquare));
    for (int i = 1; i <= 60; i++)
        issquare[i*i] = true;
}

int main() {
    initdata();

    int n;
    scanf("%d", &n);

    int flow = 0, num = 0;
    int s = 0, t = OFFSET*2 + 1;

    dc.cleardata(t + 1);

    while (num - flow <= n) {
        num += 1;
        dc.addedge(s, num, 1);
        dc.addedge(num + OFFSET, t, 1);
        for (int i = 1; i < num; i++)
            if (issquare[i+num])
                dc.addedge(i, num + OFFSET, 1);

        flow += dc.maxflow(s, t);
    }
    num -= 1;

    dc.cleardata(t + 1);
    for (int i = 1; i <= num; i++) {
        dc.addedge(s, i, 1);
        dc.addedge(i + OFFSET, t, 1);
        for (int j = 1; j < i; j++)
            if (issquare[j+i])
                dc.addedge(j, i + OFFSET, 1);
    }
    dc.maxflow(s, t);
    printf("%d\n", num);
    dc.printpath(num);

    return 0;
}