比赛 20110730 评测结果 C
题目名称 朦胧之旅 最终得分 0
用户昵称 Vani 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-30 10:21:07
显示代码纯文本
#define Debug
#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;
		Edge(int y, Edge* next):y(y), next(next){}
	}*a[MAXN];

	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 Edge(y, a[x]);
			hash[x] = 1, hash[y] = 2;
		}
	}

	bool vis[MAXN];

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

	void solve(void) {
		Input();
		int Ans = 0, bug = 0;
		for (int i = 1; i <= n; i++) if (hash[i] == 1) {
			memset(vis, 0, sizeof vis);
			Ans += Find(i);
		}
		printf("0 %d\n", n - Ans);
	}
}
int main(int argc, char** argv) {
	#ifdef Debug
		freopen("lovetravel.in", "r", stdin);
		freopen("lovetravel.out", "w", stdout);
	#endif
	Solve::solve();
	return 0;
}