bzoj1854 [Scoi2010]游戏【构图并查集】

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1854

没想到怎么做真是不应该，看到每个武器都有两个属性，应该要想到连边构图的！太不应该了！

构图之后，显然，一个有n个点的联通块要么有n - 1条边，要么有>=n条边（因为可能有重边）。由于一把武器只能使用一次，也就是说一条边只能“属于”其连接的两个点的其中一个。当有n - 1条边时，这时一棵树，这棵树里的边可以满足任意的n - 1个点，因为随便找一个点拉成有根树，使每一条边都“属于”其儿子节点就行了。那么这种情况是不是真的要“随便找一个点”呢？实则不然。因为题目要求了，要按照顺序打boss，所以应该尽量让编号更小的点得到一条边，所以应该让编号最大的点成为树根，对应程序里，在并查集union操作时，应该让编号较小的成为编号较大的儿子，然后标记编号较小的节点。当有>= n条边时，很显然所有点都可以得到一条边，岂不美哉？对应程序里，此时getfa找到的两个fa是一样的，那么就标记这个fa。

#include <cstdio>

const int maxn = 1000005;

int n, u, v, fu, fv, fa[10005], tem;

char ch, ok[10005];

int getfa(int aa) {

	return aa == fa[aa]? aa: fa[aa] = getfa(fa[aa]);

}

inline void readint(int & rt) {

	while ((ch = getchar()) < 48);

	rt = ch - 48;

	while ((ch = getchar()) > 47) {

		rt = rt * 10 + ch - 48;

	}

}

int main(void) {

	//freopen("in.txt", "r", stdin);

	readint(n);

	for (int i = 1; i < 10001; ++i) {

		fa[i] = i;

	}

	for (int i = 0; i < n; ++i) {

		readint(u);

		readint(v);

		fu = getfa(u);

		fv = getfa(v);

		if (fu == fv) {

			ok[fu] = 1;

		}

		else {

			if (fu < fv) {

				tem = fu;

				fu = fv;

				fv = tem;

			}

			fa[fv] = fu;

			ok[fv] = 1;

		}

	}

	int i;

	for (i = 1; ok[i]; ++i);

	printf("%d\n", i - 1);

	return 0;

}

巴特西

bzoj1854 [Scoi2010]游戏【构图并查集】

最新文章

热门文章

巴特西

bzoj1854 [Scoi2010]游戏【构图 并查集】

最新文章

热门文章

bzoj1854 [Scoi2010]游戏【构图并查集】