洛谷P2765 魔术球问题

[链接标题](https://www.luogu.com.cn/problem/P2765)

复习最小路径覆盖

最小路径覆盖是指对于给定的DAG，用最少的路径将其所有点覆盖，路径不相交。最小路径覆盖建图如下：
![title](https://leanote.com/api/file/getImage?fileId=6010dd06ab644110900000a4)

变式1：最小链覆盖
用最少的路径将其所有点覆盖，路径可以相交
做法：使用floyd传递闭包重连边，然后进行最小路径覆盖

变式2：最长反链
指选择最多的点，使得两两之间不能互相到达
做法：对偶问题：最长反链等于最小链覆盖

-------
本题中发现球是依次加入的，如果有两个球和为完全平方数那么小的向大的连接单向边，一个柱子就相当于一条路径。那么可以知道$K$个球最少能放到几个柱子上，因为球对柱子是单调的，那么不断增加球的个数跑网络流，找到柱子数$\le n$的最大$K$就是答案

```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
int bL[maxn], bR[maxn], ord[maxn], dcnt, S, T;
int ncnt, is_sqr[maxn];

namespace Dinic {
	struct edge {
		int v, w, next;
	} e[maxn << 3];
	int head[maxn], cnt = 1;
	void adde(const int &u, const int &v, const int &w) {
		e[++cnt] = (edge) {v, w, head[u]};
		head[u] = cnt;
		e[++cnt] = (edge) {u, 0, head[v]};
		head[v] = cnt;
	}
	int layer[maxn], iter[maxn], N;
	void init() {
		for(int i = 1; i <= N; ++i)
			iter[i] = head[i], layer[i] = 0;
	}
	int bfs(int s, int t) {
		init();
		queue<int > q;
		q.push(s), layer[s] = 1;
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = head[u]; i; i = e[i].next) {
				int v = e[i].v;
				if(!e[i].w) continue;
				if(layer[v]) continue;
				layer[v] = layer[u] + 1;
				q.push(v);
			}
		}
		return layer[t];
	}
	int dfs(int u, int t, int mflow) {
		if(u == t) return mflow;
		int ret = 0;
		for(int &i = iter[u]; i; i = e[i].next) {
			int v = e[i].v, tmp;
			if(!e[i].w) continue;
			if(layer[v] != layer[u] + 1)
				continue;
			tmp = dfs(v, t, min(mflow - ret, e[i].w));
			e[i].w -= tmp, e[i ^ 1].w += tmp;
			ret += tmp;
			if(ret == mflow)
				return ret;
		}
		return ret;
	}
	int work(int n, int s, int t) {
		N = n;
		int ans = 0;
		while(bfs(s, t)) ans += dfs(s, t, 1000000000);
		return ans;
	}
}

void add() {
	using namespace Dinic;
	int now = ++ncnt;
	bL[now] = ++dcnt;
	ord[bL[now]] = now;
	bR[now] = ++dcnt;
	ord[bR[now]] = now;
	adde(S, bL[now], 1);
	adde(bR[now], T, 1);
	for(int i = 1; i < now; ++i) {
		if(is_sqr[now + i]) {
			adde(bL[now], bR[i], 1);
		}
	}
}

vector<int > col[65];

void GetPth(int u, int id) {
	using namespace Dinic;
	col[id].push_back(u);
	for(int i = head[bL[u]]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == S || v == T) continue;
		if(!e[i].w) GetPth(ord[v], id);
	}
}

void update() {
	using namespace Dinic;
	for(int i = 1; i <= n; ++i)
		col[i].clear();
	int ccnt = 0;
	for(int i = head[T]; i; i = e[i].next) {
		int v = e[i].v;
		if(e[i].w) continue;
		GetPth(ord[v], ++ccnt);
	}
}

int main() {
	for(int i = 1; i * i <= 100000; ++i) {
		is_sqr[i * i] = 1;
	}
	scanf("%d", &n);
	S = ++dcnt, T = ++dcnt;
	int p, tmp = 0;
	for(p = 1; ; ++p) {
		add();
		tmp += Dinic::work(dcnt, S, T);
		if(p - tmp > n) break;
		update();
	}
	--p;
	printf("%d\n", p);
	for(int i = 1; i <= n; ++i) {
		for(auto j : col[i])
			printf("%d ", j);
		puts("");
	}
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链