(step6.3.4)hdu 1151(Air Raid——最小路徑覆蓋)

題意：       一個鎮裡所有的路都是單向路且不會組成回路。          派一些傘兵去那個鎮裡，要到達所有的路口，有一些或者沒有傘兵可以不去那些路口，只要其他人能完成這個任務。每個在一個路口著陸了的傘兵可以沿著街去到其他路口。我們的任務是求出去執行任務的傘兵最少可以是多少個。       思路：       這個題就是個最小路徑覆蓋問題。   路徑覆蓋的定義是：在有向圖中找一些路徑，使之覆蓋了圖中的所有頂點，就是任意一個頂點都跟那些路徑中的某一條相關聯，且任何一個頂點有且只有一條路徑與之關聯，一個單獨的頂點是一條路徑.最小路徑覆蓋就是最少的路徑覆蓋數。      如上圖，最小路徑覆蓋的那條路應該是{e1,e4,e5,e6,e7},最小路徑覆蓋就是1。       有定理： 最小路徑覆蓋 = 圖的頂點數 – 最大匹配數。       其實那個最大匹配數並 非原圖的最大匹配數，而是最小路徑覆蓋的邊的條數，是把圖中每個點拆成兩個點，再算出來的最大匹配數。很容易證明兩者是相同的。        可是有一點不明白，為什麼原圖用匈牙利算法算出最大匹配數，與圖的頂點數想減，最後求出的最小路徑覆蓋是對的呢，而不需要用拆點後的圖來算呢？   -----原來我建的鄰接表它本身就拆點了，所以不矛盾。     --------------------------以上為摘抄別的大牛的   代碼如下:  

/* 
 * 1151_1.cpp 
 * 
 *  Created on: 2013年8月31日 
 *      Author: Administrator 
 */  
#include <iostream>  
  
using namespace std;  
  
const int maxn = 1001;  
int map[maxn][maxn];  
int link[maxn];  
bool useif[maxn];  
int n;  
  
int can(int t){  
    int i;  
    for(i = 1 ; i<= n ; ++i){  
        if(useif[i] == 0 && map[t][i]){  
            useif[i] = 1;  
            if(link[i] == - 1 || can(link[i])){  
                link[i] = t;  
                return 1;  
            }  
        }  
    }  
  
    return 0;  
}  
  
int max_match(){  
    int i;  
    int num = 0;  
    memset(link,-1,sizeof(link));  
    for(i = 1 ; i <= n ; ++i){  
        memset(useif,0,sizeof(useif));  
        if(can(i)){  
            num++;  
        }  
    }  
    return num;  
}  
  
int main(){  
    int t;  
    scanf("%d",&t);  
    while(t--){  
        int k;  
        memset(map,0,sizeof(map));  
        scanf("%d%d",&n,&k);  
  
        int i;  
        for(i = 1 ; i <= k ; ++i){  
            int a,b;  
            scanf("%d%d",&a,&b);  
            map[a][b] = 1;  
        }  
  
        printf("%d\n",n - max_match());  
  
    }  
}