BZOJ

BZOJ 1854 游戏

题意

一个武器有两种属性，属性由一个[1…10000]之间的整数表示。现从属性1 向上依次递增，共n武器，每个武器只能有一次，求最多能到多少属性。

数据范围

$$n\leq1000000$$

题解

  • 做法一
    将武器和属性都看成点，并从属性向对应武器连边，这样就构成二分图，跑匈牙利。直到某一属性无法找到路径就跳出。
    但由于匈牙利算法复杂度是n^3，所以无法得满分。
  • 做法二
    满分算法是并查集。将武器看成边，属性看成点。将每个武器两个属性连边，实际上是连接两个连通块。
    首先要明白，如果一个n个点的连通块上有环，则所有属性都能取到；如果没有环（就是一棵树），则能取到n-1个属性。
    我们用布尔类型v来维护并查集。在连接两属性时，如果它们不在同一个连通块内，就把顶点小的连到顶点大的连通块上，并将定点小的v置为true；如果两属性本在同一连通块内，就将两个顶点v都置为true。这样，最后保证若一个连通块内有环，则所有点v都是true；如果没环，则只有顶点是false，且顶点是连通块内点值最大的。
    最后从小到大扫一遍所有点的v就能找到答案。

    代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<cstring>
using namespace std;
int f[10010];
bool v[10010];
int find(int x)
{
	if (f[x]!=x) return f[x]=find(f[x]);
	return x;
}
int main()
{
	int n,p,q,f1,f2,i;
	scanf("%d",&n);
	for (int i=1;i<=10000;i++) f[i]=i;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&p,&q);
		f1=find(p);f2=find(q);
		if (f1<f2) f[f1]=f2,v[f1]=true;
		else f[f2]=f1,v[f2]=true;
	}
	for (i=1;i<=n+1;i++)
	if (!v[i]) break;
	printf("%d",i-1);
	return 0;
}