題意：一個地圖上有n個小鎮，以及連接著其中兩個小鎮的有向邊，而且這些邊無法形成回路。現在選擇一些小鎮空降士兵（1個小鎮最多1個士兵），士兵能沿著邊走到盡頭，問最少空降幾個士兵，能遍歷完所有的小鎮。
思路：匈牙利算法求最小路徑覆蓋：在一個有向圖中，路徑覆蓋就是在圖中找一些路徑，使之覆蓋了圖中的所有頂點，且任何一個頂點有且只有一條路徑與之關聯；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，那麼恰好可以經過圖中的每個頂點一次且僅一次）；解決此類問題可以建立一個二分圖模型。把所有頂點i拆成兩個：Ｘ結點集中的i和Y結點集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設二分圖最大匹配為m,則結果就是n-m
代碼：
[cpp]
<span style="font-family:KaiTi_GB2312;font-size:18px;">#include<iostream>
using namespace std;
const int maxn=125;
int map[maxn][maxn],visit[maxn],match[maxn];
int n;
bool dfs(int v)
{
int i;
for(i=1;i<=n;i++)
{
if(map[v][i]&&!visit[i])
{
visit[i]=1;
if(match[i]==-1||dfs(match[i]))
{
match[i]=v;
return true;
}
}
}
return false;
}
int hungry()
{
int i,ans=0;
memset(match,-1,sizeof(match));
for(i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if(dfs(i)) ans++;
}
return ans;
}
int main()
{
int i,t,j,a,b,ans,m;
scanf("%d",&t);
while(t--) www.2cto.com
{
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=1;
}
ans=n-hungry();
printf("%d%\n",ans);
}
return 0;
}
</span>
