[网络流24题]魔术球问题（简化版）

发表于   |  

问题描述：

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

数据输入：

文件第1 行有 1个正整数n，表示柱子数。

结果输出:

文件的第一行是球数。

数据规模

n<=60 保证答案小于1600

输入文件示例

4

输出文件示例

11

HINT

方案如下

1 8
2 7 9
3 6 10
4 5 11

每一行表示一个柱子上的球

Sol

二分图的性质：
最大匹配 = 最小顶点覆盖
最大独立集 = 点数 - 最小顶点覆盖 = 最小路径覆盖
这道题是求最小路径覆盖
把DAG的点分成两个，把入边和出边分开，形成二分图
然后求最大匹配即可。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#define d(i) i + 5000
#define S 10002
#define T 10001
#define maxn 10010
#define maxm 100010
#define INF 1000000009
#define min(a,b) (a<b)?a:b
using namespace std;
int ans = 0, s = 0, n;
struct Edge
{
	int v, f, l, nex;
}ed[maxm];
int fir[maxn], e = 0;
void addedge(int u, int v, int f, int l){
	ed[++e].v = v;
	ed[e].f = f;
	ed[e].l = e - l;
	ed[e].nex = fir[u];
	fir[u] = e;
}
queue <int> q;
int dis[maxn];
bool bfs(){
	memset(dis, -1, sizeof dis);
	q.push(S);
	dis[S] = 0;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (int i = fir[u]; i; i = ed[i].nex) {
			int v = ed[i].v;
			if (ed[i].f && dis[v] == -1) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	if (dis[T] != -1) return true;
	return false;
}

int find(int u, int mf = INF){
	if (u == T) return mf;
	int flow = 0;
	for (int i = fir[u]; i; i = ed[i].nex) {
		int v = ed[i].v;
		if (ed[i].f && dis[v] == dis[u] + 1 && (flow = find(v, min(mf, ed[i].f)))) {
			ed[i].f -= flow;
			ed[ed[i].l].f += flow;
			return flow;
		}
	}
	return 0;
}

int dinic(){
	int ret = 0, flow = 0;
	while (bfs()) {
		while (flow = find(S)) {
			ret += flow;
		}  
	}
	return ret;
}

int main(){
freopen(""balla.in"", ""r"", stdin);
freopen(""balla.out"", ""w"", stdout);
	scanf(""%d"", &n);
	int s = 0, d = 0;
	while (true) {
		s++;
		for (int i = 1; i < s; i++) {
			if (sqrt(i+s) == int(sqrt(i+s))) {
				addedge(i, d(s), 1, 1);
				addedge(d(s), i, 0, -1);
			}
		}
		addedge(S, s, 1, 1);
		addedge(s, S, 0, -1);
		addedge(d(s), T, 1, 1);
		addedge(T, d(s), 0, -1);
		d += dinic();
		if (s - d > n) {
			break;
		}
	}
	printf(""%d"", s-1);
	return 0;
}