HDU 3861 The King’s Problem 强连通分量 最小路径覆盖
2024-08-29 22:48:50
先找出强连通分量缩点,然后就是最小路径覆盖。
构造一个二分图,把每个点\(i\)拆成两个点\(X_i,Y_i\)。
对于原图中的边\(u \to v\),在二分图添加一条边\(X_u \to Y_v\)。
- 最小路径覆盖 = 顶点个数 - 最大匹配数
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn = 5000 + 10;
const int maxm = 100000 + 10;
struct Edge
{
int v, nxt;
Edge() {}
Edge(int v, int nxt): v(v), nxt(nxt) {}
};
int ecnt, head[maxn];
Edge edges[maxm];
void AddEdge(int u, int v) {
edges[ecnt] = Edge(v, head[u]);
head[u] = ecnt++;
}
int n, m;
stack<int> S;
int dfs_clock, pre[maxn], low[maxn];
int scc_cnt, sccno[maxn];
void dfs(int u) {
pre[u] = low[u] = ++dfs_clock;
S.push(u);
for(int i = head[u]; ~i; i = edges[i].nxt) {
int v = edges[i].v;
if(!pre[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if(!sccno[v]) low[u] = min(low[u], pre[v]);
}
if(low[u] == pre[u]) {
scc_cnt++;
for(;;) {
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if(x == u) break;
}
}
}
void find_scc() {
dfs_clock = scc_cnt = 0;
memset(pre, 0, sizeof(pre));
memset(sccno, 0, sizeof(sccno));
for(int i = 1; i <= n; i++) if(!pre[i])
dfs(i);
}
int ecnt2, head2[maxn];
Edge edges2[maxm];
int left[maxn];
bool vis[maxn];
void AddEdge2(int u, int v) {
edges2[ecnt2] = Edge(v, head2[u]);
head2[u] = ecnt2++;
}
bool find(int u) {
for(int i = head2[u]; ~i; i = edges2[i].nxt) {
int v = edges2[i].v;
if(vis[v]) continue;
vis[v] = true;
if(!left[v] || find(left[v])) {
left[v] = u;
return true;
}
}
return false;
}
int main()
{
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
ecnt = 0;
memset(head, -1, sizeof(head));
while(m--) {
int u, v; scanf("%d%d", &u, &v);
AddEdge(u, v);
}
find_scc();
ecnt2 = 0;
memset(head2, -1, sizeof(head2));
for(int u = 1; u <= n; u++) {
for(int i = head[u]; ~i; i = edges[i].nxt) {
int v = edges[i].v;
if(sccno[u] == sccno[v]) continue;
AddEdge2(sccno[u], sccno[v]);
}
}
int match = 0;
memset(left, 0, sizeof(left));
for(int i = 1; i <= scc_cnt; i++) {
memset(vis, 0, sizeof(vis));
if(find(i)) match++;
}
printf("%d\n", scc_cnt - match);
}
return 0;
}
最新文章
- linux查看cpu 命令
- 一起买beta版UI测试
- 线上mysql内存持续增长直至内存溢出被killed分析(已解决)
- 应用Spring MVC发布restful服务是怎样的一种体验
- Encode &; decode
- javascript构造函数小记
- Ectouch修改虚拟销售数量的方法
- Hive 自定义函数(转)
- NSNumber与NSInteger的区别
- PHP - 自定义函数
- App如何选择移动广告平台的开发者3 - 选择标准广告平台
- java中自定义异常类
- 20190415 - iOS11 无法连接到 App Store 的解决办法
- 如何去掉(隐藏)系统的StatusBar(状态栏)
- 洛谷P1216数字三角形题解
- 【HDU - 4340】Capturing a country(树形DP)
- [Golang] lua战斗验证服务器
- Mac idea error=13, Permission denied
- git add .添加不成功
- Android设计和开发系列第一篇:Notifications通知(Develop—API Guides)