[CTSC 2008] 祭祀

[題目連結]

https://www.lydsy.com/JudgeOnline/problem.php?id=1143

[算法]

答案為最小路徑可重複點覆寫所包含的路徑數，将原圖G進行弗洛伊德傳遞閉包，得到一張新圖G'，然後求出拆點二分圖G2'的最大比對，N - 最大比對即為答案，我們嘗試證明上述結論：

設祭祀點集合為S，最小路徑可重複點覆寫的邊集為Path,由于Path覆寫了所有節點，故每條路徑上至多選一個點，有： |S| <= |Path| , 是以，如果我們能構造出一組解，使得| S | = | Path | ，就證明了此結論，這裡給出一種構造方案：

首先求出拆點二分圖的最大比對，設節點x在拆點二分圖上分别對應左部節點x和右部節點x' , 對于每個非比對節點x0,我們不斷通路 x0,match[x0'],match[ match[x0'] ] .. 直到最後遇到一個左部節點y0,使得其右部點y0'為非比對點，那麼就得到了一條路徑，其中y0為起點，x0為

首先我們将所有路徑的終點構成一個集合E,根據傳遞閉包的性質，兩個祭祀點之間無路徑相連，等價于在新圖G’上任意兩個祭祀點之間沒有邊，不妨讓集合E中的每個節點走一條邊，構成集合Next(E),如果E和Next(E)的交集為空集，則S = E

否則，對于交集中的每個點e,我們沿着e所在的路徑不斷向上移動，直到e不在目前的交集中，從E中删除e，加入e',重複以上過程，直到交集為空，就求出了S的一種組成方案

可以證明，在任何時刻，我們都能找到合法的e'，因為若沒有，說明e所在的路徑上所有點都可以被其他路徑上的點到達，我們可以找到到達e所在的的路徑起點的那條路徑，将其延伸，使得| Path | 減少1，并覆寫所有節點，與Path的最小性沖突

綜上所述，答案即為最小路徑可重複點覆寫所包含的路徑數

[代碼]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 210

int i,j,k,n,m,u,v,ans;
bool g[MAXN][MAXN],mp[MAXN][MAXN];
bool visited[MAXN];
int match[MAXN];

inline bool hungary(int u)
{
        int v;
        for (v = 1; v <= n; v++)
        {
                if (mp[u][v] && !visited[v])
                {
                        visited[v] = true;
                        if (!match[v] || hungary(match[v]))
                        {
                                match[v] = u;
                                return true;
                        }
                }
        }
        return false;
}

int main() 
{
        
        scanf("%d%d",&n,&m);
        for (i = 1; i <= n; i++) g[i][i] = true;
        for (i = 1; i <= m; i++)
        {
                scanf("%d%d",&u,&v);
                g[u][v] = true;
        }
        for (k = 1; k <= n; k++)
        {
                for (i = 1; i <= n; i++)
                {
                        for (j = 1; j <= n; j++)
                        {
                                g[i][j] |= g[i][k] & g[k][j];
                        }
                }
        }
        for (i = 1; i <= n; i++)
        {
                for (j = 1; j <= n; j++)
                {
                        if (i != j && g[i][j])
                           mp[i][j] = true;
                }
        }
        ans = n;
        for (i = 1; i <= n; i++)
        {
                memset(visited,false,sizeof(visited));
                if (hungary(i)) ans--;
        }
        printf("%d
",ans);
        
        return 0;
    
}