loj 1429(可相交的最小路径覆盖)

题目链接：http://lightoj.com/volume_showproblem.php?problem=1429

思路：这道题还是比较麻烦的，对于求有向图的可相交的最小路径覆盖，首先要解决成环问题，可以先染色缩点重建图，然后就是如何来处理这个路径可以相交这个问题，这里可以用bfs求出任意两点之间是否可达，如果可达，就连边，然后就是HK算法求最大匹配了，最小路径覆盖 = 顶点数 - 最大匹配。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

const int MAXN = (1000 + 10);
const int MAXM = (10000 + 10);
int n, m;
int cnt, scc_count;
bool Instack[MAXN];
int low[MAXN], dfn[MAXN], color[MAXN];
vector<int > g[MAXN];
stack<int > S;

void Tarjan(int u)
{
    low[u] = dfn[u] = ++cnt;
    Instack[u] = true;
    S.push(u);
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (dfn[v] == 0) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (Instack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_count++;
        int v;
        do {
            v = S.top();
            S.pop();
            Instack[v] = false;
            color[v] = scc_count;
        } while (u != v);
    }
}

bool Isok[MAXN][MAXN];
bool mark[MAXN];
vector<int > reg[MAXN];

void bfs(int st)
{
    memset(mark, false, sizeof(mark));
    queue<int >que;
    que.push(st);
    mark[st] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = 0; i < (int)reg[u].size(); i++) {
            int v = reg[u][i];
            if (!mark[v]) {
                mark[v] = true;
                que.push(v);
            }
        }
    }
}

void Build()
{
    for (int i = 1; i <= scc_count; i++) {
        reg[i].clear();
    }
    for (int i = 1; i <= scc_count; i++) {
        for (int j = 1; j <= scc_count; j++) {
            if (i != j && Isok[i][j]) {
                reg[i].push_back(j);
            }
        }
    }
}

int lx[MAXN], ly[MAXN];
int distx[MAXN], disty[MAXN];

bool MaxMatch_bfs()
{
    bool flag = false;
    memset(distx, 0, sizeof(distx));
    memset(disty, 0, sizeof(disty));
    queue<int > que;
    for (int i = 1; i <= scc_count; i++) {
        if (lx[i] == -1) que.push(i);
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = 0; i < (int)reg[u].size(); i++) {
            int v = reg[u][i];
            if (disty[v] == 0) {
                disty[v] = distx[u] + 1;
                if (ly[v] == -1) flag = true;
                else {
                    distx[ly[v]] = disty[v] + 1;
                    que.push(ly[v]);
                }
            }
        }
    }
    return flag;
}

int dfs(int u)
{
    for (int i = 0; i < (int)reg[u].size(); i++) {
        int v = reg[u][i];
        if (disty[v] == distx[u] + 1) {
            disty[v] = 0;
            if (ly[v] == -1 || dfs(ly[v])) {
                ly[v] = u;
                lx[u] = v;
                return 1;
            }
        }
    }
    return 0;
}

int MaxMatch()
{
    memset(lx, -1, sizeof(lx));
    memset(ly, -1, sizeof(ly));
    int res = 0;
    while (MaxMatch_bfs()) {
        for (int i = 1; i <= scc_count; i++) {
            if (lx[i] == -1) res += dfs(i);
        }
    }
    return res;
}


int main()
{
    int _case, t = 1;
    scanf("%d", &_case);
    while (_case--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            g[i].clear();
            reg[i].clear();
        }
        while (m--) {
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
        }
        //强联通缩点重建图
        cnt = scc_count = 0;
        memset(dfn, 0, sizeof(dfn));
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) Tarjan(i);
        }
        for (int u = 1; u <= n; u++) {
            for (int i = 0; i < (int)g[u].size(); i++) {
                int v = g[u][i];
                if (color[u] != color[v]) {
                    reg[color[u]].push_back(color[v]);
                }
            }
        }
        //bfs求出新图中的任意两点之间是否可达
        memset(Isok, false, sizeof(Isok));
        for (int i = 1; i <= scc_count; i++) {
            bfs(i);
            for (int j = 1; j <= scc_count; j++) {
                if (mark[j]) {
                    Isok[i][j] = true;
                }
            }
        }
        //对于那些可达的点重新连边
        Build();
        //bfs求解最大匹配；
        //最小路径覆盖 = 顶点数 - 最大匹配数
        int ans = MaxMatch();
        printf("Case %d: %d
", t++, scc_count- ans);
    }
    return 0;
}