放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1703 Find them, Catch them 题解 《挑战程序设计竞赛》

POJ 1703 Find them, Catch them

无间道:有N名来自两个帮派的坏蛋,已知一些坏蛋两两不属于同一帮派,求判断给定两个坏蛋是否属于同一帮派。

2.4 加工并储存数据的数据结构

并查集

这题真的很简单,是食物链的弱化版,使用相似的思路来做即可——

定义并查集为:

并查集里的元素i-x表示i属于帮派x

同一个并查集的元素同时成立

可见所有元素个数为2 * N,如果i表示属于帮派A,那么i + N表示属于帮派B,每次输入两个家伙不在同一帮派的时候,就合并他们分属两个帮派的元素。我认为这是最简单最好懂的算法,那些利用复杂节点带权重接着依靠大量if-else维护并查集的做法都不够美。

有个小插曲,这题如果用cin的话会TLE,浪费我不少时间试图优化算法。我还是第一次遇到会让cin TLE的数据量。换用scanf就轻松AC:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

#define MAX_N 100000 * 2 + 16
int parent[MAX_N];
int height[MAX_N];

void init(const int& n)
{
	for (int i = 0; i < n; ++i)
	{
		parent[i] = i;
		height[i] = 0;
	}
}

int find(const int& x)
{
	if (parent[x] == x)
	{
		return x;
	}
	else
	{
		return parent[x] = find(parent[x]);
	}
}

void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y)
	{
		return;
	}

	if (height[x] < height[y])
	{
		parent[x] = y;
	}
	else
	{
		parent[y] = x;
		if (height[x] == height[y])
		{
			++height[x];
		}
	}
}

bool same(const int& x, const int& y)
{
	return find(x) == find(y);
}


int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--)
	{
		int N, M;
		cin >> N >> M;
		init(N * 2);
		char message;
		int x, y;
		getchar();
		while (M--)
		{
			// cin 会导致TLE,哭笑不得
			// cin >> message >> x >> y;
			scanf("%c%d%d%*c", &message, &x, &y);
 			if (message == 'A')
 			{
 				if (same(x, y))
 				{
 					cout << "In the same gang." << endl;
 				}
 				else if (same(x, y + N))
 				{
 					cout << "In different gangs." << endl;
 				}
 				else
 				{
 					cout << "Not sure yet." << endl;
 				}
 			}
 			else
 			{
 				unite(x, y + N);
 				unite(x + N, y);
 			}
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
12605320 hankcs 1703 Accepted 1808K 391MS C++ 1584B 2014-03-09 13:36:37

稍微扯远一点,最近看完了《数学之美》这本书,里面提到了最大熵模型,也就是“包含所有可能性”的模型。这道题目其实归根结底就是保留了所有可能性,我们只知道x和y不属于同一集合,但我们不能确定究竟x属于集合A还是集合B,于是我们保留所有可能性,对x-A和x-B都做了一次记录。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1703 Find them, Catch them 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    好像不能这么写的吧
    while(T–){
    while(M–){
    }
    }
    两个while循环,第二个括号里面如果还是用”–“就会导致无限循环了,因为对于while来说,除了0是返回false之外,就算是负数也是返回true,所以m–只有第一次执行m次,之后都会执行无数次,没有停止的,最后程序要停止是因为外面的T–。你可以试一下:
    int n = 2, m = 3;
    while(n–){
    cout<<n<<endl;
    while(m–){
    cout<<"m"<<endl;
    }
    }
    会发现这个程序是无限循环在输出m的

    narip2周前 (10-02)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机