题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1054
关于匈牙利算法的博客讲解
- https://www.cnblogs.com/shenben/p/5573788.html
- https://blog.csdn.net/qq_40938077/article/details/80410356
- (摘自上面博客)
- #include<bits/stdc++.h>
- #define MAXN 9999
- using namespace std;
- int nx,ny;//nx 表示二分图左边顶点的个数, ny 表示二分图右边顶点的个数
- int m;//m 代表边的条数
- int cx[MAXN],cy[MAXN];// 如果有 cx[i]=j, 则必有 cy[j]=i, 说明 i 点和 j 点能够匹配
- int x,y;//x 点到 y 点有边
- int e[MAXN][MAXN];// 邻接矩阵
- int visited[MAXN];// 标记数组, 标记的永远是二分图右边的顶点
- int ret;// 最后结果
- int point(int u)// 这个函数的作用是寻找增广路和更新 cx,xy 数组, 如果找到了增广路, 函数返回 1, 找不到, 函数返回 0.
- {
- for(int v=1;v<=ny;v++)// 依次遍历右边的所有顶点
- {
- if(e[u][v]&&!visited[v])// 条件一: 左边的 u 顶点和右边的 v 顶点有连通边, 条件二: 右边的 v 顶点在没有被访问过, 这两个条件必须同时满足
- {
- visited[v]=1;// 将 v 顶点标记为访问过的
- if(cy[v]==-1||point(cy[v]))// 条件一: 右边的 v 顶点没有左边对应的匹配的点, 条件二: 以 v 顶点在左边的匹配点为起点能够找到一条增广路 (如果能够到达条件二, 说明 v 顶点在左边一定有对应的匹配点).
- {
- cx[u]=v;// 更新 cx,cy 数组
- cy[v]=u;
- return 1;
- }
- }
- }
- return 0;// 如果程序到达了这里, 说明对右边所有的顶点都访问完了, 没有满足条件的.
- }
- int main()
- {
- while (cin>>m>>nx>>ny)
- {
- memset(cx,-1,sizeof(cx));// 初始化 cx,cy 数组的值为 - 1
- memset(cy,-1,sizeof(cy));
- memset(e,0,sizeof(e));// 初始化邻接矩阵
- ret=0;
- while (m--)// 输入边的信息和更新邻接矩阵
- {
- cin>>x>>y;
- e[x][y]=1;
- }
- for(int i=1;i<=nx;i++)// 对二分图左边的所有顶点进行遍历
- {
- if(cx[i]==-1)// 如果左边的 i 顶点还没有匹配的点, 就对 i 顶点进行匹配
- {
- memset(visited,0,sizeof(visited));// 每次进行 point 时, 都要对 visited 数组进行初始化
- ret+=point(i);//point 函数传入的参数永远是二分图左边的点
- }
- }
- cout<<ret<<endl;
- }
- }
AC 代码:
- #include<cstdio.>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- using namespace std;
- const int maxn=1510;
- int linker[maxn];
- int vis[maxn];
- vector<int>Map[maxn];
- int n;
- bool point(int u)
- {
- for(int i=0;i<Map[u].size();i++)
- {
- if(!vis[Map[u][i]])// 如果没有访问过这个点
- {
- vis[Map[u][i]]=1;// 标记访问
- if(linker[Map[u][i]]==-1||point(linker[Map[u][i]]))
- {// 如果这条路这个点没有走过
- linker[Map[u][i]]=u;
- return 1;
- }
- }
- }
- return 0;
- }
- int hungary()// 匈牙利
- {
- int res=0;
- memset(linker,-1,sizeof(linker));
- for(int i=0;i<n;i++)
- {
- memset(vis,0,sizeof(vis));
- if(point(i)) res++;
- }
- return res;
- }
- int main()
- {
- int u,k,v;
- while(scanf("%d",&n)!=EOF)
- {
- for(int i=0;i<maxn;i++)// 初始化清空 vector
- Map[i].clear();
- for(int i=0;i<n;i++)
- {
- scanf("%d:(%d)",&u,&k);
- for(int i=0;i<k;i++)
- {
- scanf("%d",&v);
- Map[u].push_back(v);//u 可以到 v
- Map[v].push_back(u);//v 可以到 u
- }
- }
- printf("%d\n",hungary()/2);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2927654.html