记录编号 |
26985 |
评测结果 |
AAAAAAAAAA |
题目名称 |
朦胧之旅 |
最终得分 |
100 |
用户昵称 |
Vani |
是否通过 |
通过 |
代码语言 |
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;
}