网络流24题之魔术球问题

luoguP2765魔术球问题，给出n个柱子，要求柱子每次只能从最上面放球，任意相邻两个球之和为完全平方数。球编号为1、2、3....，每个球都必须放，不能不放。求最后能放多少个球，每根柱子上的球分别是什么？

luoguP2765魔术球问题

分析

这算是我做到的网络流问题的第一个变种吧，并不再能一眼看出是网络流了233333.
首先这道题对于每个球，显然可以决策，放在某个柱子还是不放。所以一开始如果不是tag上有网络流24题，大概我就会钻进DP里出不来了吧。仔细想想会发现，dp的话，状态很难存储那么那么多(基本是无法表示的，尤其对于一个球可能能放到多个柱子上)。
所以考虑贪心，贪心的做法就是找到第一个能放的地方放柱子上，放不了就放到新柱子上。然而一方面贪心不会证明正确性(题解似乎有dalao证明了正确性)，一方面我是来练网络流的233333

这道题关键的建模在于【最小路径覆盖】，可以把柱子看成是最小路径覆盖数，每个球是点，边要求完全平方数，也就是连边条件。
又知道 最小路径覆盖数字 = 顶点数 - 最大匹配数 ， 在这里我们能确定最小路径覆盖数，然后顶点数不断增加，并通过跑匈牙利或最大流求出最大匹配数。 直到顶点数 - 最大匹配数 大于 最小路径覆盖数，就说明此时已经到边界外了，即退出循环即可。
这道题还需要用到的常用套路是，对于有向图的二分图最大匹配，需要【拆点】后，再进行匹配。原因是类似于1->2->3这种情况，如果直接跑匈牙利，是很难跑出答案的，或者跑出的答案很难输出方案。所以我们要拆成1->2 2'->3，这样即可。

最后，做二分图到底该用匈牙利还是dinic呢...?

源代码

贪心

ACcode

// 直接贪心
// 找到能放的就放，不能就新开一个。
//
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 ;
int dp[maxn];

vector<int> a[maxn];
bool isPerfect( int n )
{
    int t = sqrt(n);
    if( t * t == n )
        return true ;
    return false ;
}

int main()
{
    int n ;
    cin >> n ; 
    int ans = 0 ; 
    for( int i = 1 ; i <= 10000; i++)
    {
        bool flag = false ; 
        for( int j = 1 ; j <= n ; j++)
        {
            if( dp[j] == 0 || isPerfect( *(a[j].rbegin())  + i) )
            {
                dp[j]++;
                ans++;
                a[j].push_back(i);
                flag = true ;
                break;
                //dp[j][1] = i ;
            }
        }
        if(!flag)
            break;
    }
    cout << ans << endl ;
    for( int i = 1 ; i <= n ; i++)
    {
        for( auto j : a[i] )
            cout << j << ' ' ;
        cout << endl ;
    }

    return 0 ;
}

匈牙利算法

ACcode

/**********************************************************
 * Author        : xie keyi
 * Email         : xiekeyi98@snnu.edu.cn
 * Last modified : 2018-10-17 21:34
 * Filename      : P2765网络流24题-3.cpp
 * Description   : 
 * *******************************************************/

// 把柱子看成最小路径覆盖数
// 球看成最大匹配数
// 完全平方数条件看成匹配条件（建边条件)
//
#include <bits/stdc++.h>
using namespace std;
const int maxm = 200010;
const int maxp = 5000;
const int maxn = 10010+ maxp;
struct Edge
{
    int nxt = -1 ;
    int to ;
}edge[maxm];
int tol = 0 ;
int head[maxn];

void init()
{
    tol = 0 ;
    memset(edge,-1,sizeof(edge));
    memset(head,-1,sizeof(head));
}

void addedge( int u , int v )
{
    edge[tol].to = v ;
    edge[tol].nxt = head[u];
    head[u] = tol++;
}


bool used[maxn];
int linker[maxn];

int dfs( int u )
{
    for( int i = head[u] ; ~i ; i = edge[i].nxt )
    {
        int to = edge[i].to;

        if( !used[to] )
        {
            used[to] = true ; 

            if( linker[to] == 0 || dfs( linker[to] ) )
            {
                linker[to] = u ;
                linker[u] = to ;
                return 1 ;
            }
        }

    }
    return 0 ;
}

int xiongyali()
{
    int res = 0 ; 
    memset(linker,0,sizeof(linker));
    memset(used,0,sizeof(used));
    for( int i = 1; i <= maxp ; i++ )
    {
        memset(used,0,sizeof(used));
        res += dfs( i ) ;
    }
    return res;
}

bool isPerfect( int n )
{
    int t = sqrt(n) ;
    return t * t == n ;
}

void print( int i )
{
    int t = i + maxp;
    while(  t != 0 )
    {
        t = t - maxp; 
        used[t] = true ;
        cout << t  << ' ' ;
        t = linker[t];
    }
    cout << endl ; 
}


int main()
{
    init();
    int n ;
    cin >> n ;
    int m = 0 ;
    // m 是小球数量(点数) ， n是最小路径覆盖数, ans是最大匹配数
    // 点数-最大匹配数 = 最小路径覆盖数字
    int ans = 0 ; 
    while( m - ans <= n )
    {
        m++;
        for( int i = 1 ; i <= m - 1 ; i++)
        {
            if( isPerfect(i+m) )
            {
                addedge(i , m + maxp);
                addedge(m+maxp , i);
            }
        }
    //    memset( used,0,sizeof(used));
    //    cout << "m+maxp:" << m + maxp << endl ; 
    //    ans += dfs(m+maxp);
        ans =  xiongyali(m)   ;
        // 为什么从拆的点（Y部)匈牙利就会对，
        // 从原点1到n匈牙利，方案就会不一样？
    m--;
    cout << m << endl;
    memset(used,0,sizeof(used));
    for( int i = 1 ; i <= m ; i++)
    {
        if( !used[i] )
            print(i);
    }
    return 0 ;
}