[数据结构与算法]P2765 Dinic

题意

传送门 P2765 魔术球问题

题解

将满足 $x+y$ 为完全平方数的数字 $x,y$ 连边，考虑到从小到大依次放入数字，那么建一条有向边 $\min (x,y)\to \max (x,y)$。于是得到一个 $DAG$。

若数字 $1?num$ 可以放到 $n$ 个柱子上，则等价于 $DAG$ 可以找到一组规模为 $n$ 的最小路径覆盖的路径数。那么依次增大 $num$，求 $DAG$ 的最小路径覆盖即可，这个问题等价于求拆点二分图上的最大匹配（路径划分中的最多的前驱节点数）。

若新增一个节点 $num+1$，匹配数至多增加一，此时最小路径覆盖数不变；反之，最小路径覆盖数增加一，若这个值恰好大于 $n$，则 $num$ 为所求。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int MAXV = 1e5, INF = 0x3f3f3f3f;
int N, V;
struct edge
{
    int to, cap, rev;
};
vector<edge> G[MAXV];
int iter[MAXV], level[MAXV];

void add_edge(int from, int to, int cap)
{
    G[from].pb({to, cap, G[to].size()});
    G[to].pb({from, 0, G[from].size() - 1});
}

void bfs(int s)
{
    for (int v = 0; v < V; ++v)
        level[v] = -1;
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (q.size())
    {
        int v = q.front();
        q.pop();
        for (auto &e : G[v])
            if (e.cap > 0 && level[e.to] == -1)
                level[e.to] = level[v] + 1, q.push(e.to);
    }
}

int dfs(int v, int t, int f)
{
    if (v == t)
        return f;
    for (int &i = iter[v]; i < G[v].size(); ++i)
    {
        auto &e = G[v][i];
        if (e.cap > 0 && level[e.to] > level[v])
        {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0)
            {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t)
{
    int flow = 0;
    for (;;)
    {
        bfs(s);
        if (level[t] == -1)
            return flow;
        for (int v = 0; v < V; ++v)
            iter[v] = 0;
        int f;
        while ((f = dfs(s, t, INF)) > 0)
            flow += f;
    }
}

int in[MAXV], nxt[MAXV];

bool judge(int x)
{
    int k = 0;
    while (k * k < x)
        ++k;
    return k * k == x;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N;
    int s = 0, t = 1;
    V = t + 1;
    int num = 1, flow = 0;
    for (;; ++num)
    {
        V += 2;
        add_edge(s, num * 2, 1);
        add_edge(num * 2 + 1, t, 1);
        for (int i = 1; i < num; ++i)
            if (judge(i + num))
                add_edge(i * 2, num * 2 + 1, 1);
        flow += max_flow(s, t);
        if (num - flow > N)
        {
            --num;
            break;
        }
    }
    memset(in, 0, sizeof(in));
    memset(nxt, -1, sizeof(nxt));
    for (int i = 1; i <= num; ++i)
    {
        for (auto &e : G[i * 2])
            if (e.to != s && e.cap == 0)
            {
                int j = (e.to - 1) / 2;
                ++in[j], nxt[i] = j;
                break;
            }
    }
    cout << num << '\n';
    for (int i = 1; i <= num; ++i)
        if (in[i] == 0)
        {
            int v = i;
            while (v != -1)
                cout << v << ' ', v = nxt[v];
            cout << '\n';
        }
    return 0;
}