Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
30行,438MS的CPP代码#include<cstdio> #include<cstring> using namespace std; const int N = 500, M = 20000; int n, hd[N], to[M], nt[M], vis[N], mc[N], tot, ans; inline void addEdge(int x, int y) { nt[tot] = hd[x], to[tot] = y, hd[x] = tot++; } inline bool find(int u) { for (int i = hd[u]; ~i; i = nt[i])if (!vis[to[i]] && (vis[to[i]] = 1)) if (mc[to[i]] == -1 || find(mc[to[i]])) { mc[to[i]] = u; return true; } return false; } signed main(void) { while (scanf("%d", &n) != EOF) { memset(mc, -1, n << 2); memset(hd, -1, n<<2), tot = 0; for (int i = 0, x, y, z; i < n; i++) { scanf("%d: (%d)", &x, &y); for (int j = 0; j < y; j++) scanf("%d", &z), addEdge(x, z); } for (ans = tot = 0; tot < n; tot++) memset(vis, 0, sizeof(vis)), ans += find(tot); printf("%d\n", n - (ans >> 1)); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator