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

本文主要是介绍「网络流 24 题」魔术球【最小路径覆盖】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

「网络流 24 题」魔术球

注意这里的球是依次放置，也就是说如果当前放到第 $i$ 号球，那么 $\rarr i - 1$ 号球都已经放好了，否则可以放无数个球

思路

首先我们对于 $i < j 且 i + j = 完全平方数$ 连边： $\rarr j$
并且我们假设当前我们要构造答案 $x$ ，也就是说 $[1, x]$ 号球我们都要放好
那么对于这张有 $x$ 个点的有向无环图，我们等价于要找一些路径去覆盖整张图，并且路径数越少越好！同一路径上的点就表示我们将这些球按顺序放在同一柱子上

我们可以从小到大枚举答案 $n$ ，并且在之前的基础上添加新的有向边 $\rarr n \quad if \quad i + n = 完全平方数$ ，然后跑一个最小路径覆盖，判断所需的柱子数是否小于等于给定的柱子数即可

时间复杂度： $\cdot (n + nm))，m$ 为边数

// Problem: #6003. 「网络流 24 题」魔术球
// Contest: LibreOJ
// URL: https://loj.ac/p/6003
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long longconst int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;typedef long long ll;const int N = 2500;std::vector<int> match; //match[i]表示每个右点i当前匹配的左点
std::vector<bool> used; //当前轮 右点 i 是否被预定
std::vector<int> g[N];bool dfs(int l){ //为当前左点 l 寻找匹配for(auto r : g[l])if(!used[r]){ //如果当前轮右点r还没有被预订used[r] = true; //预定if(!match[r] || dfs(match[r])){match[r] = l;return true;
//（1）如果右点 r 还没有配对
//（2）右点 r 已经配对，尝试更换其原配左点}}return false;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int k;std::cin >> k;int cnt = 0;fore(n, 1, N){match.assign(n + 1, 0);fore(i, 1, n){ //在原先的基础上加边int w = i + n;int rt = sqrt(w);if(rt * rt != w)	continue;g[i].push_back(n);}int num = 0; //最大匹配数fore(i, 1, n + 1){used.assign(n + 1, false);num += dfs(i);}num = n - num; //最小路径覆盖if(num > k)	break; //柱子不够cnt = n;}std::cout << cnt << endl;std::vector<int> nxt(cnt + 1, 0);std::vector<bool> head(cnt + 1, true);fore(v, 1, cnt + 1){int u = match[v];if(!u)	continue;head[v] = false;nxt[u] = v;}fore(i, 1, cnt + 1){if(!head[i])	continue;int u = i;while(nxt[u]){std::cout << u << ' ';u = nxt[u];}std::cout << u << endl;}return 0; 
}