最小路径覆盖与强连通分量的应用：国王的问题

在静默王国中，国王面临一个新的难题。王国中有N个城市，M条单向道路连接这些城市。这意味着如果有一条从u到v的道路，则只能从u前往v，而不能反向行驶。为了更有效地管理王国，国王希望将王国划分为若干个州，每个城市必须属于且仅属于一个州。

此外，对于每对城市(u, v)，如果可以从u到达v并且可以从v到达u，则这两个城市必须属于同一个州。同时，国王要求在每个州内，任意两个城市之间至少可以互相到达，而不经过其他州的城市。

现在国王请求你的帮助，他想知道最少需要划分多少个州。

第一行包含一个整数T，表示测试用例的数量。接下来是T个测试用例。

每个测试用例的第一行包含两个整数n和m（0

输出应包含T行。对于每个测试用例，输出一个整数，表示最少需要划分的州的数量。

2011年多校联合训练赛第三场 - 北京理工大学承办

题目解析：这是一个有向图划分问题，目标是最小化划分的区域数量。

规则如下：

1. 如果有边从u到v且有边从v到u，则u和v必须划分到同一区域内。


2. 一个区域内的任意两点至少要有一方能到达另一方。


3. 每个点只能划分到一个区域内。

解题思路：根据规则1，首先需要对强连通分量进行缩点，缩点后形成一个新的弱连通图。然后根据规则2和3，问题转化为求该图的最小路径覆盖。

定义：

• 最小路径覆盖：在图中找一些路径（路径数最少），使之覆盖所有顶点，且每个顶点只与一条路径相关联。


• 最小顶点覆盖：在图中找一些点（顶点数最少），使之覆盖所有边，每条边至少与一个顶点相关联。


• 二分图：最小顶点覆盖等于最大匹配数。


• 最小路径覆盖 = 顶点数 - 最大匹配数。

相关资源：

• 二分图最小路径覆盖：链接


• 匈牙利算法：链接

代码实现：

#include
#include
#include
#include
using namespace std;
vector s[5050];
stack st;
int vt[5050];
int cnt, ct;
int low[5050], dfn[5050];
int bl[5050], nd[5050];
struct Edge {
    int x, y;
} mp[100050];
int min(int a, int b) {
    return a <= b ? a : b;
}
void tarjan(int a) {
    low[a] = dfn[a] = ++cnt;
    vt[a] = 1;
    st.push(a);
    for (int i = 0; i         int u = s[a][i];
        if (!dfn[u]) {
            tarjan(u);
            low[a] = min(low[a], low[u]);
        } else if (vt[u])
            low[a] = min(low[a], dfn[u]);
    }
    if (low[a] == dfn[a]) {
        ++ct;
        do {
            int x = st.top();
            vt[x] = 0;
            nd[x] = ct;
            st.pop();
        } while (st.top() != a);
        st.pop();
    }
}
bool find(int a) {
    for (int i = 0; i         int u = s[a][i];
        if (!vt[u]) {
            vt[u] = 1;
            if (bl[u] == 0 || find(bl[u])) {
                bl[u] = a;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(dfn, 0, sizeof(dfn));
        memset(vt, 0, sizeof(vt));
        memset(bl, 0, sizeof(bl));
        ct = cnt = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            s[i].clear();
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &mp[i].x, &mp[i].y);
            s[mp[i].x].push_back(mp[i].y);
        }
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                tarjan(i);
        int sum = 0;
        for (int i = 1; i <= n; ++i)
            s[i].clear();
        for (int i = 1; i <= m; ++i) {
            int u = nd[mp[i].x], v = nd[mp[i].y];
            if (u != v)
                s[u].push_back(v);
        }
        for (int i = 1; i <= ct; ++i) {
            memset(vt, 0, sizeof(vt));
            if (find(i))
                ++sum;
        }
        printf("%d\n", ct - sum);
    }
    return 0;
}