首页 > 代码库 > HDU2063过上车【匈牙利】

HDU2063过上车【匈牙利】

2024-07-16 04:58:45   218人阅读

大意：同学们去坐过山车，但是想要去做过山车必须是一个男同学一个女同学一起坐，

现在告诉你每个女同学想要跟那些人一起坐，问最多能有多少对同学能够坐过山车

男女同学人数都是<=500

 

思路：

将女同学跟其喜欢的男同学连一条边，然后求二分图的最大匹配即可。

也可以用最大流来做，将源点与女同学之间建立一个容量为1的边，将女同学与其喜欢的男同学都建立一条容量为1的边，最后将男同学与汇点建立一条容量为1的边jike，求出最大刘即可。

 

匈牙利算法，人数很少直接用的邻接矩阵存储的

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 505; 7 bool G[maxn][maxn]; 8 int Left[maxn]; 9 bool vis[maxn];10 int n, m;11 12 bool Find(int u) {13     for(int i = 1; i <= m; i++) {14         if(G[u][i] && !vis[i]) {15             vis[i] = true;16             if(Left[i] == -1 || Find(Left[i])) {17                 Left[i] = u;18                 return true;19             }20         }21     }22     return false;23 }24 25 void solve() {26     int num = 0;27     memset(Left, -1, sizeof(Left));28     for(int i = 1; i <= n; i++) {29         memset(vis, 0, sizeof(vis));30         if(Find(i)) num++;31     }32     printf("%d\n",num);33 }34 35 int main() {36     int k;37     int u, v;38    // freopen("a.txt","r",stdin);39     while(scanf("%d",&k) && k) {40         scanf("%d %d",&n, &m);41         memset(G, false, sizeof(G));42         for(int i = 0; i < k; i++) {43             scanf("%d %d",&u, &v);44             G[u][v] = 1;45         }46         solve();47     }48     return 0;49 }
View Code

 


联系
我们