记录编号 26985 评测结果 AAAAAAAAAA
题目名称 朦胧之旅 最终得分 100
用户昵称 GravatarVani 是否通过 通过
代码语言 C++ 运行时间 0.017 s
提交时间 2011-07-30 15:10:10 内存使用 0.44 MiB
显示代码纯文本
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cctype>
namespace Solve {
	const int MAXN = 5010;

	inline int ScanInt(void) {
		int r = 0, c;
		while (!isdigit(c = getchar()));
		r = c - '0';
		while ( isdigit(c = getchar())) r = r * 10 + c - '0';
		return r;
	}
	
	struct Edge {
		int y; Edge *next;
		inline Edge(int y, Edge* next):y(y), next(next){}
		inline Edge(){}
		inline void* operator new (size_t, void* t) {return t;}
	}*a[MAXN], POOL[MAXN << 1], *data = POOL;

	int n, m, s, List[MAXN], link[MAXN], hash[MAXN], bug;

	inline void Input(void) {
		bug = n = ScanInt(), m = ScanInt(), s = ScanInt();
		while (s--) {
			int x = ScanInt(), y = ScanInt(); ScanInt();
			a[x] = new((void*)data++) Edge(y, a[x]);
			hash[x] = 1, hash[y] = 2;
		}
	}

	int vis[MAXN], flag; bool match[MAXN];

	bool Find(int u) {
		for (Edge *p = a[u]; p; p = p->next)
			if (vis[p->y] != flag) {
				vis[p->y] = flag;
				if (link[p->y] == 0 || Find(link[p->y])) {
					link[p->y] = u;
					return true;
				}
			}
		return false;
	}

	inline void solve(void) {
		Input();
		int Ans = 0, bug = 0;
	/*	for (int i = 1; i <= n; i++) if (hash[i] == 1)
			for (Edge *p = a[i]; p; p = p->next) if (!link[p->y]) {
				link[p->y] = i;
				match[i] = true; Ans++;
				break;
			}*/
		for (int i = 1; i <= n; i++) if (!match[i] && hash[i] == 1) {
		//	memset(vis + 1, 0, sizeof (bool) * n);
			flag++;
			Ans += Find(i);
		}
		printf("0 %d\n", n - Ans);
	}
}
int main(int argc, char** argv) {
	freopen("lovetravel.in", "r", stdin);
	freopen("lovetravel.out", "w", stdout);
	Solve::solve();
	return 0;
}