在一個(gè)ＰＸＰ的有向圖中，路徑覆蓋就是在圖中找一些路經(jīng)，使之覆蓋了圖中的所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián)；（如果把這些路徑中的每條路徑從它的起始點(diǎn)走到它的終點(diǎn)，那么恰好可以經(jīng)過(guò)圖中的每個(gè)頂點(diǎn)一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個(gè)弱連通子集．
由上面可以得出：
１.一個(gè)單獨(dú)的頂點(diǎn)是一條路徑；
２．如果存在一路徑p1,p2,......pk，其中p1 為起點(diǎn)，pk為終點(diǎn)，那么在覆蓋圖中，頂點(diǎn)p1,p2,......pk不再與其它的頂點(diǎn)之間存在有向邊．
最小路徑覆蓋就是找出最小的路徑條數(shù)，使之成為Ｐ的一個(gè)路徑覆蓋．
路徑覆蓋與二分圖匹配的關(guān)系：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；
其中最大匹配數(shù)的求法是把Ｐ中的每個(gè)頂點(diǎn)pi分成兩個(gè)頂點(diǎn)pi'與pi''，如果在p中存在一條pi到pj的邊，那么在二分圖Ｐ＇中就有一條連接pi'與pj''的無(wú)向邊；這里pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；
對(duì)于公式：最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)；可以這么來(lái)理解；
如果匹配數(shù)為零，那么Ｐ中不存在有向邊，于是顯然有：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數(shù)＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路徑覆蓋數(shù)為｜Ｐ｜；
Ｐ＇中不在于匹配邊時(shí)，路徑覆蓋數(shù)為｜Ｐ｜；
如果在Ｐ＇中增加一條匹配邊pi'－－＞pj''，那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說(shuō)pi與pj 在一條路徑上，于是路徑覆蓋數(shù)就可以減少一個(gè)；
如此繼續(xù)增加匹配邊，每增加一條，路徑覆蓋數(shù)就減少一條；直到匹配邊不能繼續(xù)增加時(shí)，路徑覆蓋數(shù)也不
能再減少了，此時(shí)就有了前面的公式；但是這里只
是說(shuō)話了每條匹配邊對(duì)應(yīng)于路徑覆蓋中的一條路徑上的一條連接兩個(gè)點(diǎn)之間的有向邊；下面來(lái)說(shuō)明一個(gè)路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的有向邊對(duì)應(yīng)于一條匹配
邊；
與前面類(lèi)似，對(duì)于路徑覆蓋中的每條連接兩個(gè)頂點(diǎn)之間的每條有向邊pi--->pj，我們可以在
匹配圖中對(duì)應(yīng)做一條連接pi'與pj''的邊，
顯然這樣做出來(lái)圖的是一個(gè)匹配圖（這一點(diǎn)用反證法很容易證明，如果得到的圖不是一個(gè)匹配圖，那么這個(gè)圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ，那邊從pi出發(fā)的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類(lèi)似可證）；
至此，就說(shuō)明了匹配邊與路徑覆蓋圖中連接兩頂點(diǎn)之間邊的一一對(duì)應(yīng)關(guān)系，那么也就說(shuō)明了前面的公式成立！
1 #include <iostream>
2 using namespace std;
3 int n,m;
4 int map[250][250];
5 bool visit[500];
6 int l[500];//鄰接點(diǎn)
7 bool find(int a)
8 {
9 for(int i=1;i<=n;++i)
10 if(map[2*a][2*i-1]&&!visit[2*i-1])
11 {
12 visit[2*i-1]=1;
13 if(!l[2*i-1]||find(l[2*i-1]))
14 {
15 l[2*i-1]=a;
16 return true;
17 }
18 }
19 return false;
20 }
21 int main()
22 {
23 int cas,a,b;
24 scanf("%d",&cas);
25 for(int i=1;i<=cas;++i)
26 {
27 memset(l,0,sizeof(l));
28 memset(map,0,sizeof(map));
29 scanf("%d%d",&n,&m);
30 //把節(jié)點(diǎn)分成兩個(gè)節(jié)點(diǎn)，2*i是出節(jié)點(diǎn),2*i-1是如節(jié)點(diǎn)
31 for(int j=1;j<=m;++j)
32 {
33 scanf("%d%d",&a,&b);
34 map[2*a][2*b-1]=1;
35 }
36 int ans=0;
37 for(int i=1;i<=n;++i)
38 {
39 memset(visit,0,sizeof(visit));
40 if(find(i))ans++;
41 }
42 printf("%d\n",n-ans);
43 }
44 return 0;
45 }