[BJOI2012]连连看 题解

link

关于 Dijkstra+EK 实现的费用流。
考虑将算法中的 spfa 替换成 Dijsktra，但由于有负边，考虑乱搞势能函数将边权全部弄成正数。
一个很显然的错解是 \(\forall e_i，e_i=e_i+\min\{e\}\)，因为我们不知道最短路径上有几条路。

定义势能函数 \(del_i\)。把 \(x\) 到 \(y\) 的边权从 \(e_{x,y}\) 换成 \(del_u-del_v+e_{u,v}\)，并且能保证对于任意一条边，\(del_u-del_v \geqslant -e_{u,v}\)，那么图中就没有负边了，我们就可以继续使用 Dijkstra。

而且我们考虑从起点 \(S\) 到 \(T\) 的一条路径，如果每条边都这样处理，实际上路径上除了 \(S\) 到 \(T\) 之外的其他点的势函数都被抵消了，最后得到的路径权值是原始路径长度加上 \(del_S-del_T\)，这样我们求出最短路之后，只需要加上 \(del_T\) 减去 \(del_S\)。一般来说 \(del_T=0\)。

这里提供一种构造方法，我们令 上一次的最短路径 \(dp_i\) 为这次的 \(del_i\)。
考虑两种情况：

  1. 上次增广此条边没变，根据最短路的性质：\(dp_y\leqslant dp_x+e_{x,y}\)，符合上述条件。
  2. 上次增广后此条边被加，那么此条边的反边一定在最短路径上，那么 \(dp_y=dp_x+e_{x,y}\)，显然满足 \(dp_y-dp_x\geqslant -(-e_{x,y})\)（此时取等）。

故上述构造方法合理。如果刚开始有负边，我们要先跑一遍 spfa 求出最短路径，如果没有，直接令 \(del_i=0\) 亦可。

回归本题。
板子。考虑搞成二分图，两边都连（即 \(x\) 连 \(y+n\)，\(y\) 连 \(x+n\)），贪心地来想，一组最优的匹配肯定是两条边都取，于是连边跑完后 \(ans\) 除以 \(2\) 即可。注意求最大边权取负。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mr make_pair
#define pr pair  
#define LL long long
using namespace std;
const int MAXN = 2000 + 5, MAXM = 505 * 505 * 2 + 1005 * 2, inf = 0x3f3f3f3f;
struct Node {
	int X, Y, Z, C;
}edge[MAXM];
int n, m, S, T, flowmax, cstmin, flow[MAXN], dp[MAXN], del[MAXN];
int Head[MAXN], Next[MAXM], tot = 1, pre[MAXN], id[MAXN];
bool vis[MAXN];
queue  q;
priority_queue , greater  > que;
int Min(int x, int y) { return x < y ? x : y; }
void Add(int x, int y, int z, int c) {
	tot ++; edge[tot].X = x; edge[tot].Y = y; edge[tot].Z = z; edge[tot].C = c; Next[tot] = Head[x]; Head[x] = tot;
}
void addedge(int x, int y, int z, int c) {
	Add(x, y, z, c); Add(y, x, 0, -c);
}
bool bfs() {
	int t, y, z, c;
	for(int i = 0; i <= T; i ++) flow[i] = dp[i] = inf, vis[i] = 0;
	vis[S] = 1; que.push(mr(0, S)); dp[S] = 0;
	while(!que.empty()) {
		t = que.top().second; que.pop(); vis[t] = 1;
		for(int i = Head[t]; i; i = Next[i]) {
			y = edge[i].Y, z = edge[i].Z, c = edge[i].C + del[edge[i].X] - del[y];
			if(!vis[y] && edge[i].Z > 0 && dp[t] + c < dp[y]) {
				dp[y] = dp[t] + c; pre[y] = t; id[y] = i; flow[y] = Min(flow[t], z);
				que.push(mr(dp[y], y));
			}
		}
	}
    return (dp[T] != inf);
}
void spfa() {
	int t, y, c;
	q.push(S);
	for(int i = 0; i <= T; i ++) dp[i] = inf, vis[i] = 0;
	vis[S] = 1; dp[S] = 0;
	while(!q.empty()) {
		t = q.front(); q.pop(); vis[t] = 0;
		for(int i = Head[t]; i; i = Next[i]) {
			y = edge[i].Y; c = edge[i].C;
			if(dp[t] + c < dp[y] && edge[i].Z) {
				dp[y] = dp[t] + c;
				if(!vis[y]) q.push(y), vis[y] = 1;
			}
		}
	}
	for(int i = 0; i <= T; i ++) del[i] += (dp[i] == inf ? 0 : dp[i]);
}
void Dinic() {
	while(bfs()) {
		int now = T; flowmax += flow[T]; cstmin += flow[T] * (dp[T] + del[T]);
		while(now != S) edge[id[now]].Z -= flow[T], edge[id[now] ^ 1].Z += flow[T], now = pre[now];
		for(int i = 0; i <= T; i ++) del[i] += (dp[i] == inf ? 0 : dp[i]);
	}
}
int check(int x) {
	int t = sqrt(x);
	return (t * t == x) ? t : 0; 
}
int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; }
int main() {
	int U, V;
	scanf("%d%d", &U, &V); n = V - U + 1; S = 0; T = 2 * n + 1;
	for(int i = U; i <= V; i ++) {
		addedge(S, i - U + 1, 1, 0);
		addedge(n + i - U + 1, T, 1, 0);
		for(int j = i + 1; j <= V; j ++) {
			if(check(j * j - i * i) && Gcd(check(j * j - i * i), i) == 1) {
				addedge(i + 1 - U, n + j + 1 - U, inf, -i - j);
				addedge(j + 1 - U, n + i + 1 - U, inf, -i - j);
			}	
		}
	}
	spfa(); Dinic(); printf("%d %d", flowmax / 2, -cstmin / 2);
	return 0;
}
网络流费用流

相关

图论---网络流

网络流 学习笔记

Codeforces 1373F - Network Coverage（模拟网络流）

网络流24题-骑士共存

【网络流24题】最长不下降子序列问题

网络流各算法超详细带源码解析

python 方法无法在线程中使用（附python获取网络流量）

[教程]网络流详解: 从入门到放弃

网络流基础知识

网络流（二）

[知识点]网络流基础

【网络流】CF708D Incorrect Flow

标签