洛谷 P2765 魔术球问题

题目描述：

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。

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

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

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

«编程任务：

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

解法：

我们要求的是n根柱子最多能串起来多少个球（编号连续），即为最小路径覆盖问题，由于一个球不能放在两个柱子上，所以是最小不相交路径覆盖。

这题为给定路径数，求能被覆盖的点数最多有多少。求最小路径覆盖可以用二分图来解决。见https://www.cnblogs.com/obob/p/9642644.html

这题由于解题思路是逐个增加球数，然后看是否可行，不能每次都重新建图，那时间肯定炸了。所以做法是每次新加一个球之后，以这个球为起点跑增广路，如果这个点能找到匹配点，那就不用加柱子，不然加柱子。

我的二分图是用网络流写的（毕竟这是网络流24题）

代码：

//最大流Dinic算法
//m为边数,n为点数
//复杂度O(m*n*n)
#include <bits/stdc++.h>
using namespace std;
#define N 5005
#define M 200005
int INF = 0x3f3f3f3f;
int dep[N],head[N];
int to[N];//当前弧优化

struct Edge{
    int to,next,w;
}edge[M<<1];
int cnt = 0;
//edge[i] 的反向边为 dege[i^1]

int s,t;//s->源,t->汇

void ad(int x,int y,int w){
    edge[cnt].to = y,edge[cnt].next = head[x],edge[cnt].w = w,head[x] = cnt++;
    edge[cnt].to = x,edge[cnt].next = head[y],edge[cnt].w = 0,head[y] = cnt++;
}

bool D_bfs(){
    memset(dep,0,sizeof(dep));
    memset(to,0,sizeof(to));
    dep[s] = 1;
    queue<int> Q;
    while(!Q.empty()) Q.pop();
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i = head[u];i != -1;i = edge[i].next){
            int v = edge[i].to;
            if(edge[i].w > 0 && !dep[v]){
                dep[v] = dep[u] + 1;
                Q.push(v);
            }
        }
    }
    if(dep[t]) return 1;
    return 0;
}

int D_dfs(int u,int now){
    if(u == t) return now;
    int beg = to[u] ? to[u] : head[u];
    for(int i = beg;i != -1;i = edge[i].next){
        int v = edge[i].to;
        if(dep[v] == dep[u] + 1 && edge[i].w > 0){
            int di = D_dfs(v,min(now,edge[i].w));
            if(di == 0) continue;
            
            edge[i].w -= di;
            edge[i^1].w += di;
            if(edge[i].w) to[u] = i;
            else to[u] = edge[i].next;
            return di;
        }
    }
    return 0;
}

int Dinic(){
    int sum = 0,flow;
    while(D_bfs()){
        while((flow = D_dfs(s,INF)))
            sum += flow;
    }
    return sum;
}
void init(){
    memset(head,-1,sizeof(head));
    cnt = 0;
}
bool vis[5005];
void print(int now){
    vis[now] = 1;
    for(int i = head[now<<1];i != -1;i = edge[i].next){
        if(edge[i].w == 0 && edge[i].to != 1){
            printf("%d ",now);
            print(edge[i].to>>1);
            return;
        }
    }
    printf("%d\n",now);
}

int main()
{
    init();
    int n;
    s = 1,t = 5000;
    cin >> n;
    int ball = 0;
    int now = 0;
    while(now <= n){
        ++ball;
        ad(s,ball<<1,1);
        for(int i = 1;i < ball;++i){
            int tmp = sqrt(ball+i);
            if(tmp*tmp == ball + i)
                ad(i<<1,ball<<1|1,1);
        }
        ad(ball<<1|1,t,1);
        if(!Dinic()) now++;
    }
    cout << ball - 1 << endl;
    for(int i = 1;i <= ball-1;++i){
        if(!vis[i]){
            print(i);
        }
    }
    return 0;
}