[coci2015-2016 coii] dijamant【图论】

传送门：http://www.hsin.hr/coci/archive/2015_2016/

进去之后的最下面的国家赛。顺便说一句，dijamant是克罗地亚语的“钻石”的意思。

官方题解是说压位的暴力可以AC，但是给出了一个更棒的算法，是这样的：只考虑如何判断“diamond”，因为前两个子任务实在是太容易了。设Pi为当前声明的类继承的第i个类。那么当声明一个类时，先读取其继承的类，读进P，然后对P按“由刚刚声明的类到最早声明的类”排序，换句话说，就是从大到小排（当然了，如果使用stl的map，一定是越早成功声明的类，编号越小）。然后，维护一个布尔型的R数组，若Ri为true，表明当前正在声明的类可以从第i个类派生（derive）出来。那么分两种情况：

①，若Pi已经被标记，即R[Pi] = true，则直接ignore

②，若Pi未被标记，则将所有可以派生出Pi的类全部标记，并且如果某个可以派生出Pi的类已经被标记，则说明出现了一个diamond，声明类失败。

上述内容仔细想想、画画图就有了，确实挺巧妙的。

#include <iostream>

#include <string>

#include <algorithm>

#include <map>

#include <cstring>

const int maxn = 1005, maxe = 1000006;

int head[maxn], to[maxe], next[maxe], lb;

int n, P[maxn], idx, cnt;

char R[maxn];

std::string str, now;

std::map<std::string, int> mp;

inline void ist(int aa, int ss) {

	to[lb] = ss;

	next[lb] = head[aa];

	head[aa] = lb;

	++lb;

}

bool cmp(const int aa, const int ss) {

	return aa > ss;

}

int main(void) {

	freopen("dijamant.in", "r", stdin);

	freopen("dijamant.out", "w", stdout);

	memset(head, -1, sizeof head);

	memset(next, -1, sizeof next);

	std::cin >> n;

	char flag;

	int tem;

	int nn = n;

	while (nn--) {

		flag = 0;

		std::cin >> now;

		if (mp.count(now)) {

			std::cout << "greska\n";

			flag = 1;

		}

		std::cin >> str;

		if (flag) {

			while (1) {

				std::cin >> str;

				if (!strcmp(str.c_str(), ";")) {

					break;

				}

			}

			continue;

		}

		idx = 0;

		memset(R, 0, sizeof R);

		while (1) {

			std::cin >> str;

			if (!strcmp(str.c_str(), ";")) {

				break;

			}

			if (!flag) {

				if (!mp.count(str)) {

					flag = 1;

					std::cout << "greska\n";

				}

				else {

					P[idx++] = mp[str];

				}

			}

		}

		if (flag) {

			continue;

		}

		std::sort(P, P + idx, cmp);

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

			tem = P[i];

			if (R[tem]) {

				P[i] = -1;

				continue;

			}

			for (int j = head[tem]; j != -1; j = next[j]) {

				if (R[to[j]]) {

					flag = 1;

					std::cout << "greska\n";

					goto spe;

				}

				else {

					R[to[j]] = 1;

				}

			}

		}

		spe:;

		if (flag) {

			continue;

		}

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

			if (R[i]) {

				ist(cnt, i);

			}

		}

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

			if (P[i] != -1) {

				ist(cnt, P[i]);

			}

		}

		std::cout << "ok\n";

		mp[now] = cnt;

		++cnt;

	}

	return 0;

}

巴特西

[coci2015-2016 coii] dijamant【图论】

最新文章

热门文章