hdu1150 二分图匹配的最小点覆盖

本文主要是介绍hdu1150 二分图匹配的最小点覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <string.h>using namespace std;const int MAXN = 101;
int n, m;int c[MAXN][MAXN];
int match[MAXN];
bool vis[MAXN];void init()
{memset(match, -1, sizeof(match));
}bool dfs(int u)
{for (int i = 1; i < m; i++)//从1开始,到m{if (c[u][i] && !vis[i]){vis[i] = true;if (match[i] == -1 || dfs(match[i])){match[i] = u;return true;}}}return false;
}void solve()
{int ans = 0;for (int i = 1; i < n; i++)//从1开始{memset(vis, false, sizeof(vis));if (dfs(i)){ans++;}}cout << ans << endl;
}void input()
{int num;while (cin >> n, n){cin >> m >> num;init();int x, u, v;memset(c, 0, sizeof(c));for (int i = 0; i < num; i++){cin >> x >> u >> v;c[u][v] = 1;}solve();}
}int main()
{input();return 0;
}

这篇关于hdu1150 二分图匹配的最小点覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---