洛谷P2065 [TJOI2011] 卡片

题目描述

桌子上现在有m张蓝色卡片和n张红色卡片，每张卡片上有一个大于1的整数。现在你要从桌子上拿走一些卡片，分若干次拿。每次只能拿走一组卡片：这组卡片颜色不同，并且两张卡片上面的数字的最大公约数大于1。问：最多可以从桌上拿走多少组卡片。

输入格式

每个输入文件中包含多组测试数据，每个文件中测试数据的数目不超过100。

文件的第一行读入一个整数T，为数据组数。

每组数据的格式如下：

m n

b1 b2 … bm

r1 r2 … rn

第二行给出每张蓝色卡片上面的数字，第三行给出每张红色卡片上的数字。

输出格式

对每组测试数据，输出最多可以拿走多少张卡片。

输入输出样例

输入 #1

7
4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961

输出 #1

3
1
0
4
9
18
85

说明/提示

对100%的数据：1<=t<=100;

1<=m,n<=500;

卡片上的数字大于1，小于10 000 000。

思路

首先这道题不难想到是用O(n^2)的方法来给二分图建边，然后再跑一个最大匹配，然而对于这种做法，假设一种最简单的情况就是两种颜色各有500张，每张上的数字都为2，那么就乱了，因为边的数量有500^2即250000条，而一边点又有500个，那么跑二分图的时候假设每个未盖点都去把对面的已盖点都遍历一遍再找到一个未盖点，那么这个过程中就又浪费了一些时间，总之就是对于每个点都会大概把前面的很多条边全部遍历一遍，复杂度O(nm)，这样最差可以到1e9以上的水平，就很容易超时，因此要采用洛谷题解中大佬展示的最大流算法，证明不难，复杂度更低，顶多1e8，代码如下：

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<numeric>
#include<stack>
#include<queue>
#include<set>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f, int_max = 0x7fffffff, maxn = 505, ofst = 2 * maxn, s = 501, dst = 502, maxn2 = 1e5 + 5;
//offset是偏移量方便数字和因子建立边
//不妨把源节点设置为501，汇点设置为502
//通过质因子建边然后跑Dinic，最差差不多1e8，相关推导如下：
// //下面是直接O(n^2)建边的复杂度
// cout<<100*(500*500*log2(1e7)/*建边复杂度*/+500*(500*500)/*nm，如每个数字都一样就可以是500*500*/)<<"\n";
// //1.30813e+10，不t我t谁？！
// //下面是找质因子连边+Dinic的复杂度
// //100*(500*sqrt(1e7)/*找质因子连边*/+sqrt(1100/*差不多也就这些*/)*(500*2*10)/*最多也不到十个吧，顺便算上那个和源点汇点连接的边*/);
// cout<<100*(500*sqrt(1e7)/*找质因子连边*/+sqrt(1100/*差不多也就这些*/)*(500*2*10)/*最多也不到十个吧，顺便算上那个和源点汇点连接的边*/);
// //1.9128e+08，这个复杂度还是可以接受的
// //如果我还是要用二分图，但是更换建边方式，就是同个集合（有同质因子）的去建边，然而这样还是在时间空间上都是劣于流算法的，因此还不如直接就用上面的第二种做法
int a, b, arr1[maxn], arr2[maxn], head[maxn2], ecnt = 0, d[maxn2], vis[maxn2], cur[maxn2];
struct edge {
	int v, nxt, cap, flow;
}g[maxn * 100];
void addedge(int u, int v, int flag)
{
	g[ecnt].flow = 0;
	g[ecnt].cap = flag;
	g[ecnt].v = v;
	g[ecnt].nxt = head[u];
	head[u] = ecnt++;
}
bool bfs()
{
	memset(d, 63, sizeof d);
	memset(vis, 0, sizeof vis);
	queue<int> q;
	q.push(s);
	d[s] = 0;
	vis[s] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = head[u]; ~i; i = g[i].nxt)
		{
			edge &e = g[i];
			if (!vis[e.v] && e.cap > e.flow)
			{
				vis[e.v] = 1;
				d[e.v] = d[u] + 1;
				q.push(e.v);
			}
		}
	}
	return vis[dst];
}
ll dfs(int u, ll fi)
{
	if (u == dst || !fi)return fi;
	ll flow = 0, fo;
	for (int &i = cur[u]; ~i; i = g[i].nxt)
	{
		edge &e = g[i];
		if (d[u] + 1 == d[e.v] && (fo = dfs(e.v, min(fi, (ll)e.cap - e.flow))) > 0)
		{
			e.flow += fo;
			g[i ^ 1].flow -= fo;
			flow += fo;
			fi -= fo;
			if (!fi)break;
		}
	}
	return flow;
}
void display()
{
	for (int i = 0; i < 1e5; i++)
	{
		if (d[i] < inf)cout << "i=" << i << " d=" << d[i] << "\n";
	}
	cout << "\n";
}
ll maxFlow()
{
	ll flow = 0;
	while (bfs())
	{
		memcpy(cur, head, sizeof cur);
		flow += dfs(s, (ll)inf*inf);
	}
	return flow;
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		ecnt = 0;
		memset(head, -1, sizeof head);
		cin >> a >> b;
		for (int i = 0; i < a; i++)
		{
			addedge(s, i, 1);
			//cout << "？\n";
			addedge(i, s, 0);
			cin >> arr1[i];
			for (int j = 1; j*j <= arr1[i]; j++)
			{
				if (arr1[i] % j == 0)
				{
					if (j != 1)
					{
						addedge(i, ofst + j, 1);
						addedge(ofst + j, i, 0);
					}
					if (j*j != arr1[i])
					{
						addedge(i, ofst + arr1[i] / j, 1);
						addedge(ofst + arr1[i] / j, i, 0);
					}
				}
			}
		}
		for (int i = 0; i < b; i++)
		{
			addedge(i + maxn, dst, 1);
			addedge(dst, i + maxn, 0);
			cin >> arr2[i];
			for (int j = 1; j*j <= arr2[i]; j++)
			{
				if (arr2[i] % j == 0)
				{
					if (j != 1)
					{
						addedge(ofst + j, i + maxn, 1);
						addedge(i + maxn, ofst + j, 0);
					}
					if (j*j != arr2[i])
					{
						addedge(ofst + arr2[i] / j, i + maxn, 1);
						addedge(i + maxn, ofst + arr2[i] / j, 0);
					}
				}
			}
		}
		cout << maxFlow() << "\n";
	}
 
	return 0;
}