二分图最大匹配算法实例代码
时间: 2023-10-22 17:17:11 浏览: 57
好的,以下是二分图最大匹配的实例代码:
```
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 500 + 10; // 顶点数的最大值
const int MAXM = 100000 + 10; // 边数的最大值
struct Edge
{
int to, next;
} edge[MAXM];
int head[MAXN], tot;
void init()
{
tot = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int linker[MAXN];
bool used[MAXN];
int uN, vN;
bool dfs(int u)
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (!used[v])
{
used[v] = true;
if (linker[v] == -1 || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(linker, -1, sizeof(linker));
for (int u = 0; u < uN; u++)
{
memset(used, false, sizeof(used));
if (dfs(u)) res++;
}
return res;
}
int main()
{
int m;
scanf("%d%d%d", &uN, &vN, &m);
init();
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u - 1, v - 1); // 节点编号从0开始
}
printf("%d\n", hungary());
return 0;
}
```
请注意,以上代码只是二分图最大匹配算法的一个实例,实际应用中可能需要根据具体情况进行调整和修改,如节点编号是否从0开始等。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)