本文主要是介绍HDU 3861 The King’s Problem（强连通+二分图最小路径覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 3861 The King’s Problem
题目链接
题意：给定一个有向图，求最少划分成几个部分满足下面条件
互相可达的点必须分到一个集合
一个对点(u, v)必须至少有u可达v或者v可达u
一个点只能分到一个集合
思路：先强连通缩点，然后二分图匹配求最小路径覆盖
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;const int N = 5005;int t, n, m;
vector<int> g[N];
stack<int> S;int pre[N], dfn[N], sccn, sccno[N], dfs_clock;void dfs(int u) {pre[u] = dfn[u] = ++dfs_clock;S.push(u);for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!pre[v]) {dfs(v);dfn[u] = min(dfn[u], dfn[v]);} else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);}if (dfn[u] == pre[u]) {sccn++;while (1) {int x = S.top(); S.pop();sccno[x] = sccn;if (x == u) break;}}
}void find_scc() {sccn = dfs_clock = 0;memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));for (int i = 1; i <= n; i++)if (!pre[i]) dfs(i);
}int left[N], vis[N];
vector<int> scc[N];bool match(int u) {for (int i = 0; i < scc[u].size(); i++) {int v = scc[u][i];if (vis[v]) continue;vis[v] = 1;if (!left[v] || match(left[v])) {left[v] = u;return true;}}return false;
}int hungary() {memset(left, 0, sizeof(left));int ans = 0;for (int i = 1; i <= sccn; i++) {memset(vis, 0, sizeof(vis));if (match(i)) ans++;}return sccn - ans;
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) g[i].clear();int u, v;while (m--) {scanf("%d%d", &u, &v);g[u].push_back(v);}find_scc();for (int i = 1; i <= sccn; i++) scc[i].clear();for (int u = 1; u <= n; u++) {for (int j = 0; j < g[u].size(); j++) {int v = g[u][j];if (sccno[u] == sccno[v]) continue;scc[sccno[u]].push_back(sccno[v]);}}printf("%d\n", hungary());}return 0;
}这篇关于HDU 3861 The King’s Problem（强连通+二分图最小路径覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
