首页 > 代码库 > HDU 3861 The King’s Problem(强连通+二分图最小路径覆盖)
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(强连通+二分图最小路径覆盖)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。