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 |
爆汉、跑了3.6s,附我的代码,大牛们指点指点啊,不胜感激.Orz//有好的代码给我份啊:smwwh@qq.com //二分图的最大匹配数 //模板开始 #include<iostream> using namespace std; #define MAXN 501 #define MAXM 501 //map[i][j]用来表示i,j是否可达 bool map[MAXN][MAXM]; bool used[MAXM]; int match[MAXM]; //N: 匹配方个数 (都是从1开始,1-N) //M: 被匹配方个数 int N, M; bool dfs(int k) { for(int i=1; i<=M; i++) { if(!used[i] && map[k][i]) { used[i] = 1; if(match[i] == -1 || dfs(match[i])) { match[i] = k; return 1; } } } return 0; } int hungary() { int max = 0; memset(match, -1, sizeof(match)); for(int i=1; i<=N; i++) { memset(used, 0, sizeof(used)); if(dfs(i)) max++; } return max; //返回最大匹配数 } //模板结束 int main() { //freopen("in.txt", "r", stdin); int stu, girl, boy, num, max; while(scanf("%d", &stu) != EOF) { N = M = stu; memset(map, 0, sizeof(map)); for(int i=0; i<stu; i++) { scanf("%d%*c", &girl); scanf(" (%d)", &num); if(num != 0) { while(num--) { scanf("%d", &boy); map[girl+1][boy+1] = 1; } } } //最大独立集数D = 顶点数V - 最小点覆盖数C //最小点覆盖数C = 最大匹配数M max = hungary(); printf("%d\n", N - (max+1)/2); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator