首页 > 代码库 > HDU 2063 (匈牙利算法) 过山车

HDU 2063 (匈牙利算法) 过山车

2024-07-20 16:37:46   221人阅读

有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 (匈牙利算法) 过山车


联系
我们