「网络流 24 题」魔术球 最小路径覆盖

Posted on | In , ,

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1,2,3,4,⋯的球。
每次只能在某根柱子的最上面放球。
在同一根柱子中，任何2个相邻球的编号之和为完全平方数。n根柱子上最多能放多少个球。

题目链接

题解

  • 每根柱子都可以看成一条路径
  • 问题可以转化为1~ans的最小路径覆盖$\le$n
  • 不断增加数字加边做增广路即可
  • 输出方案：通过edges.flow是否满载判断递归输出即可

代码

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<bits/stdc++.h>
using namespace std;
const int maxn = 20005;
const int INF=1e9+7;

int n, m, u, v;

struct Edge
{
    int from, to, cap, flow;
    Edge(int u,int v,int c,int f):from(u), to(v), cap(c), flow(f) {}
};

struct Dinic
{
    int n, m, s, t;       // 节点数,边数(包括反向弧),源点编号和汇点编号
    vector<Edge> edges;   // 边数。edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    bool vis[maxn];      // BFS使用
    int d[maxn];          // 从起点到i的距离
    int cur[maxn];        // 当前弧下标

    void init()
    {
        for(int i=0; i<=n; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        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) //只考虑残量网络中的弧
                {
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0)
            return a;
        int flow=0, f;
        for(int& i=cur[x]; i<G[x].size(); i++) // 从上次考虑的弧
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1 == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)
                    break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t)
    {
        this->s=s;
        this->t=t;
        int flow=0;
        while(BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
};

int id[maxn], rid[maxn];
bool vis[maxn];
int to[maxn];

int main()
{
    Dinic now;
    scanf("%d", &n);
    int st=0, ed=10002;
    int cnt=0, i;
    int ans=0;
    for(i=1;i-ans<=n+1;i++)
    {
    //-    ++i;
        id[i]=++cnt;
        rid[i]=++cnt;
        now.Addedge(st,id[i],1);
        now.Addedge(rid[i], ed,1);
        for(int j=1;j<i;j++)
        {
            int k=sqrt(i+j);
            if(k*k == (i+j))
            {
                now.Addedge(id[j], rid[i], 1);
            }
        }
        ans+= now.Maxflow(st, ed);
    }
    printf("%d\n", i-2);
    for(int i=1;i<cnt-1;i+=2)
    {
        for(int j=0;j<now.G[i].size();j++)
        {
            Edge& e=now.edges[now.G[i][j]];
            if(e.flow == 1)
            {
                to[i]=e.to-1;
                break;
            }
        }
    }
    for(int i=1;i<cnt-1;i+=2)
    {
        if(!vis[i])
        {
            int x=i;
            while(x)
            {
                printf("%d ", (x+1)/2);
                vis[x]=1;
                x=to[x];
            }
            printf("\n");
        }
    }
}