Treasure Exploration

我又回来了！！！！

这是典型的求最小可相交路径覆盖
我们先求闭包，利用闭包连边，然后求解最小不可相交路径就可以了。
什么？如何求解最小不可相交路径覆盖？
点数-最大匹配数

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int max_n = 550;
const int inf = 2e9;
struct edge{
    int to,next;
}E[max_n*max_n*max_n];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;E[cnt].next = head[from];
    head[from]=cnt++;
}
int leftTo[max_n], rightTo[max_n];
int distleft[max_n], distright[max_n];
int dist;

bool seacherpath(int left_tot, int right_tot) {
    fill(distleft, distleft + left_tot + 1, -1);
    fill(distright, distright + right_tot + 1, -1);
    queue<int> que;dist = inf;
    for (int i = 1;i <= left_tot;++i)
        if (leftTo[i] == -1)
            que.push(i);
    while (!que.empty()) {
        int u = que.front();que.pop();
        if (distleft[u] > dist)break;
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (distright[v] != -1)continue;
            distright[v] = distleft[u] + 1;
            if (rightTo[v] == -1)dist = distright[v];
            else {
                distleft[rightTo[v]] = distright[v] + 1;
                que.push(rightTo[v]);
            }
        }
    }return dist != inf;
}
bool matchpath(int u) {
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (distright[v] != distleft[u] + 1)continue;
        if (distright[v] == dist && rightTo[v] != -1)continue;
        distright[v] = -1;
        if (rightTo[v] == -1 || matchpath(rightTo[v])) {
            leftTo[u] = v;
            rightTo[v] = u;
            return true;
        }
    }return false;
}

int HK(int left_tot, int right_tot) {
    fill(leftTo, leftTo + left_tot + 1, -1);
    fill(rightTo, rightTo + right_tot + 1, -1);
    int ans = 0;
    while (seacherpath(left_tot, right_tot)) {
        for (int i = 1;i <= left_tot;++i)
            if (leftTo[i] == -1 && matchpath(i))
                ++ans;
    }return ans;
}
bool tr[550][550];
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)){
        if (n==m&&n==0)break;
        fill(head,head+n+5,0);
        for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        tr[i][j]=0;
        cnt=1;
        for (int i=1,u,v;i<=m;++i){
            scanf("%d %d",&u,&v);
            tr[u][v]=1;
        }

        for (int k=1;k<=n;++k)
        for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        tr[i][j]=tr[i][k]&tr[k][j]|tr[i][j];

        for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        if (tr[i][j])
        add(i,j);

        printf("%d\n",n-HK(n,n));
    }
}