nkoj4134题解

提供一个兼具跑得慢和码量大两大优点的神笔做法/kk

很容易想到这样一个费用流建图：若一对 $(x,y)$ 是合法的，则源点向 $x$ 以及 $y$ 向汇点都连容量为 $1$ 费用为 $0$ 的边，$x$ 向 $y$ 连容量 $1$ 费用 $x+y$ 的边，答案即为最大费用最大流。

问题是我们怎么知道哪些点向源点连哪些向汇点连？（这里其它题解直接拆点解决了，不需要搞清楚哪些连源点哪些连汇点）。

以本人的数学水平无法找出一个简单的规律进行染色。但我们染色的本质，是将所有点划分为两个不交集合 $S,T$，使得所有满足 $x\in S,y\in S,x\ne y$ 的 $(x,y)$ 都不合法。同样，满足 $x\in T,y\in T,x\ne y$ 的 $(x,y)$ 也不合法。假设 $S$ 为黑色， $T$ 为白色，这样就避免了同色点之间的连边。

那么，如果一对 $(x,y)$ 合法，意味着 $x,y$ 不能划分到相同的集合里面去。可以用 2-SAT 找出一种可行方案。找到了合法的集合划分方案（染色方案）后，按照之前说的费用流建图就可以了。

2-SAT 会不会无解？这个菜鸡无法严格证明，但凭直觉满足条件的 $(x,y)$ 应该是很少的，2-SAT 的边也就很少，即 2-SAT 有解的概率很大。并且写完程序跑一遍极限数据发现 2-SAT 有解，所以这不是乱搞，是理论上没法证明但实际上无法 hack 掉的奇怪做法（

#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>

int n;
struct TwoSAT {
	struct Edge {
		int to, nxt;
	} e[4000005];
	int head[2000005], s[2000005], tot, top;
	bool mark[2000005];
	void clear() {
		memset(head, 0, sizeof head);
		memset(mark, 0, sizeof mark);
		tot = 0;
	}
	inline void AddEdge(const int u, const int v) {
		e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	}
	inline void addclause(int x, int valx, int y, int valy) {
		x = (x - 1) * 2 + valx;
		y = (y - 1) * 2 + valy;
		AddEdge(x ^ 1, y);
		AddEdge(y ^ 1, x);
	}
	bool dfs(const int u) {
		if (mark[u ^ 1]) return false;
		if (mark[u]) return true;
		mark[u] = true;
		s[top ++] = u;
		for (int i = head[u]; i; i = e[i].nxt)
			if (!dfs(e[i].to)) return false;
		return true;
	}
	bool solve() {
		for (int i = 0; i < n << 1; i += 2)
			if (!mark[i] && !mark[i ^ 1]) {
				top = 0;
				if (!dfs(i)) {
					while (top > 0) mark[s[-- top]] = false;
					if (!dfs(i ^ 1)) return false;
				}
			}
		return true;
	}
} solver;

const int INF = 1e9;
int gcd(int n, int m) {return m ? gcd(m, n % m) : n;}
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, cap, cost, nxt;
} e[200005];
int head[1005], cur[1005], dis[1005], Maxflow, Maxcost;
bool mp[1005][1005];
int tot = 1, s, t;
bool vis[1005], mark[1005];
std::queue<int> Q;
inline void AddEdge(int u, int v, int cap, int cost) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}
bool SPFA() {
	memcpy(cur, head, sizeof cur);
	memset(vis, 0, sizeof vis);
	memset(dis, ~0x3f, sizeof dis);
	memset(mark, 0, sizeof mark);
	Q.push(s);
	dis[s] = 0;
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (e[i].cap && dis[u] + e[i].cost > dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] > -INF;
}

int dfs(int u, int flow) {
	if (u == t) return flow;
	vis[u] = true;
	int used = 0, tmp;
	for (int i = cur[u]; i && used <= flow; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dis[u] + e[i].cost == dis[e[i].to]) {
			int v = e[i].to;
			if (!vis[v] && (tmp = dfs(v, min(flow - used, e[i].cap))))
				used += tmp, e[i].cap -= tmp, e[i ^ 1].cap += tmp;
		}
	}
	return used;
}

void Dinic() {
	int flow;
	while (SPFA()) Maxflow += (flow = dfs(s, INF)), Maxcost += flow * dis[t];
}

bool check(int x, int y) {
	int z = sqrt(x * x - y * y);
	return z * z == x * x - y * y && gcd(y, z) == 1;
}

int main() {
	int l, r;
	scanf("%d%d", &l, &r);
	n = r;
	s = 0, t = r + 1;
	for (int i = l; i <= r; ++ i) if (i & 1)
		for (int j = l; j < i; ++ j)
			if (check(i, j)) {
				mp[i][j] = mp[j][i] = true;
				solver.addclause(i, 1, j, 1);
				solver.addclause(i, 0, j, 0);
			}
	if (!solver.solve()) return 114514;
	for (int i = l; i <= r; ++ i)
		if (solver.mark[i * 2 - 1]) AddEdge(s, i, 1, 0);
		else AddEdge(i, t, 1, 0);
	for (int i = l; i <= r; ++ i) if (solver.mark[i * 2 - 1])
		for (int j = l; j <= r; ++ j)
			if (!solver.mark[j * 2 - 1] && mp[i][j]) AddEdge(i, j, 1, i + j);
	Dinic();
	printf("%d %d", Maxflow, Maxcost);
}