首页 > 代码库 > HDU 2063 (匈牙利算法) 过山车
HDU 2063 (匈牙利算法) 过山车
有m个妹子和n男生,男生和女生之间互相有好感则连一条线,问最多能撮合出多少对
这篇博文写的很好,没有让人望而生畏的图论术语
http://blog.csdn.net/dark_scope/article/details/8880547
核心思想就是一个“腾”字,没有妹子了不要紧,让前面的哥们换一个心仪的妹子,看看能否把自己心仪的妹子“腾”出来
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 505; 8 int line[maxn][maxn], used[maxn], girl[maxn]; 9 int k, m, n;10 11 bool find(int x)12 {13 for(int j = 1; j <= m; ++j)14 {15 if(line[x][j] && !used[j])16 {17 used[j] = 1;18 if(girl[j] == 0 || find(girl[j]))19 {20 girl[j] = x;21 return true;22 }23 }24 }25 return false;26 }27 28 int main(void)29 {30 #ifdef LOCAL31 freopen("2063in.txt", "r", stdin);32 #endif33 34 while(scanf("%d", &k) == 1 && k)35 {36 scanf("%d%d", &n, &m);37 memset(line, 0, sizeof(line));38 memset(girl, 0, sizeof(girl));39 for(int i = 0; i < k; ++i)40 {41 int a, b;42 scanf("%d%d", &a, &b);43 line[a][b] = 1;44 }45 int match = 0;46 for(int i = 1; i <= n; ++i)47 {48 memset(used, 0, sizeof(used));49 if(find(i)) ++match;50 }51 printf("%d\n", match);52 }53 return 0;54 }
HDU 2063 (匈牙利算法) 过山车
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。