闲人の题解 P2065

一道网络流的题，重在建图

题目传送门

题目分析

首先，我们简化一下题面：

有两堆数。
一次只能在两堆中分别选一个数且不互质。
求最多能取几次。
$1 \le n,m\le 500$

错误解

其实比较容易理解，所以我们首先想到了用二分做：

如果一个蓝色数字和一个红色数字不互质，我们就把它们连起来。
然后用一个二分跑一遍，求出最大匹配。

但是实际操作上是要T掉的，因为二分匹配有着 $O(nm)$ 的时间复杂度，加上连线的时间是一定会T掉的。

正解

然后啊，我就想到可以用网络流：

因为蓝色数字和红色数字互质时才可以配对，所以可以看成蓝色的数字和红色的数字是通过它们共同的质因数连接起来的。
由于每一张牌只能用一次，所以每一条流的流量都为1。
我们把源点和每一个蓝色点连起来，把每一个红色点和汇点连起来，蓝色点和红色点由中间的质数点连起来。
最后跑一遍网络流就好了。

其中在算质数点的时候，直接用试除法就可以了，不过感兴趣的同学可以了解一下Pollard's Rho算法。

Pollard's Rho

~~(不是我写的)~~

建图

接下来，还有一个问题需要解决，就是我们应该如何给点标号呢？

这里分享一种方法：

因为中间的质数点个数我们是事先不知道的，所以标号红点应该放在通过蓝点算质数点的操作之后。
由此可得：

源点为“0”号点，
蓝点编号为1到 blue，
质数点编号为 blue 到 blue + total，
红点编号为 blue + total 到 blue + total + red，
汇点编号为 blue + red + total + 1。

下面是通过样例中第一个数据所建得图：

代码

最后放上AC代码，希望可以帮助大家理解

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1000010, M = 2000010, INF = 1e9;

long long head[N], edge[M], next_[M], ver[M], tot;
int  q[N], d[N], cur[N];
int n, m, S, T;
int red, blue, total;
int p[35500], b[35500]; 

int min_(int x, int y){
	if(x < y) return x;
	return y;
}

void add(int x, int y, int z){
	ver[tot] = y, edge[tot] = z, next_[tot] = head[x], head[x] = tot ++;
	ver[tot] = x, edge[tot] = 0, next_[tot] = head[y], head[y] = tot ++;
}

void divide(int x, int e){								//用试除法找质数点并连接 
	
	int y = 0;
	for (int o = 2; o <= sqrt(x); o ++){
		if(x % o == 0) {
			p[++ y] = o;
			while (x % o == 0) x /= o;
		}
	}
	if(x > 1) p[++ y] = x;
	for(int o = 1;o <= y; o ++) {
		if(b[p[o]] != 0) add(e, b[p[o]] + red + blue, 1);
		else b[p[o]] = ++ total, add(e, b[p[o]] + red + blue, 1);
	}
	return ;
}

void divide_2(int x,int e){
	int y = 0;
	for (int o = 2; o <= sqrt(x); o ++){
		if(x % o == 0) {
			p[++ y] = o;
			while (x % o == 0) x /= o;
		}
	}
	if(x > 1) p[++ y] = x;
	for(int o = 1;o <= y; o ++) {
		if(b[p[o]] != 0) add(b[p[o]] + red + blue, e, 1);
	}
	return ;
}

bool bfs() {												
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = head[S];
	while (hh <= tt) {
		int t = q[hh++];
		for (int i = head[t]; ~i; i = next_[i]) {
			int ver_ = ver[i];
			if (d[ver_] == -1 && edge[i]) {
				d[ver_] = d[t] + 1;
				cur[ver_] = head[ver_];						 
				if (ver_ == T) return true;
				q[++ tt] = ver_;
			}
		}
	}
	return false;   
}

int find(int u, int limit) {									 
	if(u == T) return limit;
   	int flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = next_[i]) {
		cur[u] = i;
		int ver_ = ver[i];
		if (d[ver_] == d[u] + 1 && edge[i]) {
			int t = find(ver_, min_(edge[i], limit - flow));
			if (!t) d[ver_] = -1;
			edge[i] -= t, edge[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

int dinic() {												 //dinic 跑网络流 
	int r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
}

int num;

int main(){
	cin >> num;
	
	for(int w = num; w > 0; w --){
		tot = 0;
		memset(head, -1, sizeof head);
		memset(p, 0, sizeof p);
		memset(b, 0, sizeof b);
		total = 0;
		cin >> blue >> red;
		for(int j = 1;j <= blue; j++){					//接点 
			add(0, j, 1);
		}
		for(int j = 1;j <= blue; j++){
			int blue_;
			cin >> blue_;
			divide(blue_, j);
		}
		for(int i = 1; i <= red; i++){
			int red_;
			cin >> red_;
			divide_2(red_, i + blue);
		}
		
		for(int i = 1; i <= red; i++){
			add(i + blue, red + blue + total + 1, 1);
		}
		S = 0;
		T = blue + red + total + 1;
		cout << dinic() << endl;
	}
	return 0;
}