1739: 魔术球问题——最小路径覆盖

1739: 魔术球问题——最小路径覆盖

题意：

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。 （1）每次只能在某根柱子的最上面放球。 （2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。 试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可 放11 个球。 编程任务： 对于给定的n，计算在n根柱子上最多能放多少个球。

思路：

初始点数为1，每次点数加一，添加新边，求一次最小路径覆盖，判断这个值是否大于n，是则退出，不是则继续循环。

#include #include #include #include #include #include #include using namespace std;const int maxn = 10010;const int INF = 0x3f3f3f3f;struct Edge { int from, to, cap, flow, flag;};struct Dinic { int s, t; vector edges; vector G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from, int to, int cap, int flag) { edges.push_back(Edge{from, to, cap, 0, flag}); edges.push_back(Edge{to, from, 0, 0, flag}); int m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool bfs() { memset(vis, 0, sizeof(vis)); queue 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; }}ac;vector G[maxn];int vis[maxn];void dfs(int u) { if (vis[u]) return; vis[u] = true; printf("%d ", u); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; dfs(v); }}int main() { int n; scanf("%d", &n); int s = 0, t = 10001; int ans = 1, maxf = 0; while (true) { for (int i = 1; i < ans; i++) { int x = sqrt(i+ans); if (x * x != i + ans) continue; ac.addedge(i, ans+5000, 1, 1); } ac.addedge(s, ans, 1, 0); ac.addedge(ans+5000, t, 1, 0); maxf += ac.maxflow(s, t); if (ans - maxf > n) break; ans++; } printf("%d\n", ans-1); memset(vis, 0, sizeof(vis)); for (int i = 0; i < ac.edges.size(); i += 2) { if (ac.edges[i].flag == 1 && ac.edges[i].flow == 1) { int u = ac.edges[i].from, v = ac.edges[i].to; G[u].push_back(v-5000); } } for (int i = 1; i < ans; i++) { if (vis[i]) continue; dfs(i); printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。