[HDU][ACM]The King’s Problem
海胖子 - 2014/08/13题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3861
好题,同时检测 Tarjan 模板和 Hungry 模板。
题目大意:一个有向图,让你按规则划分区域,要求划分的区域数最少。
规则如下:
1、有边u到v以及有边v到u,则u,v必须划分到同一个区域内。
2、一个区域内的两点至少要有一方能到达另一方。
3、一个点只能划分到一个区域内。
解题思路:
根据规则1可知必然要对强连通分量进行缩点,缩点后变成了一个弱连通图。
根据规则2、3可知即是要求图的最小路径覆盖。
定义:
最小路径覆盖:在图中找一些路径(路径数最少),使之覆盖了图中所有的顶点,且每个顶点有且仅和一条路径有关联。
最小顶点覆盖:在图中找一些点(顶点数最少),使之覆盖了图中所有的边,每条边至少和一个顶点有关联。
二分图:最小顶点覆盖=最大匹配数。最小路径覆盖=顶点数-最大匹配数。
/* * Author: Haipz * School: HDU * File Name: 3861.cpp */ #include <cstdio> #include <cmath> #include <ctime> #include <cctype> #include <cfloat> #include <cstdlib> #include <cstring> #include <climits> #include <iostream> #include <vector> #include <string> #include <stack> #include <queue> #include <set> #include <map> #include <algorithm> using namespace std; const int N = 5000, M = 100000; int first[N + 5], girst[N + 5]; struct edge { int v, pre; } f[M + 5], g[M + 5]; int low[N + 5], dfn[N + 5]; int belong[N + 5], inStack[N + 5], Stack[N + 5]; int top, index, bcnt; void addEdge(int k, int u, int v) { f[k].v = v, f[k].pre = first[u], first[u] = k; return; } void _addEdge(int k, int u, int v) { g[k].v = v, g[k].pre = girst[u], girst[u] = k; return; } void Tarjan(int u) { Stack[top++] = u, inStack[u] = 1; low[u] = dfn[u] = ++index; for (int i = first[u]; i; i = f[i].pre) { int v = f[i].v; if (dfn[v] == 0) { Tarjan(v); low[u] = min(low[v], low[u]); } else if (inStack[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]){ ++bcnt; int v; do { v= Stack[--top]; inStack[v] = 0; belong[v] = bcnt; } while( u!=v ); } } void init(int n) { top = bcnt = index = 0; for (int i = 1; i <= n; ++i) belong[i] = i; memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(inStack, 0, sizeof(inStack)); return; } bool vis[N + 5]; int link[N + 5]; bool find(int x) { for (int i = girst[x]; i; i = g[i].pre) if (!vis[g[i].v]) { vis[g[i].v] = true; if (link[g[i].v] == -1 || find(link[g[i].v])) { link[g[i].v] = x; return true; } } return false; } int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); init(n); memset(first, 0, sizeof(first)); for (int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); addEdge(i, u, v); } for (int i = 1; i <= n; ++i) if (!dfn[i]) Tarjan(i); memset(girst, 0, sizeof(girst)); m = 0; for (int i = 1; i <= n; ++i) { int u = belong[i]; for (int j = first[i]; j; j = f[j].pre) { int v = belong[f[j].v]; if (u != v) _addEdge(++m, u, v); } } memset(link, -1, sizeof(link)); int key = 0; for (int i = 1; i <= bcnt; ++i) { memset(vis, false, sizeof(vis)); if (find(i)) ++key; } printf("%d\n", bcnt - key); } return 0; }
转载保留版权:http://haipz.com/blog/i/5714 - 海胖博客