题意：一个城镇有n个路口，m条路。每条路单向，且路无环。现在派遣伞兵去巡逻所有路口，伞兵只能沿着路走，且每个伞兵经过的路口不重合。求最少派遣的伞兵数量。

建图之后的就转化成邮箱无环图的最小路径覆盖问题。注意伞兵经过的路口不重合，这很重要，否则需要用传递闭包（Floyd）来辅助建图。

最小路径覆盖覆盖=顶点数-最大匹配。

注意是 n - 最大匹配  不是2n

 

其实。。。我看原题好久 也没看出来   经过的路口不重合 这句话。。。英语烂是原罪。。。啊啊啊啊

 

#include 
      
       #include
       
        #include
        
         #include
         
          #define N 220 using namespace std; int mp[N][N],v[N],linker[N],n,m; int dfs(int t){    for(int i=1;i<=n;i++)    {        if(!v[i]&&mp[t][i])        {            v[i]=1;            if(linker[i]==-1||dfs(linker[i]))            {                linker[i]=t;                return 1;            }        }    }    return 0;} int hungary(){    memset(linker,-1,sizeof(linker));    int ans=0;    for(int i=1;i<=n;i++)    {        memset(v,0,sizeof(v));        if(dfs(i))  ans++;    }    return ans;} int main(){    int T;    cin>>T;    while(T--)    {        cin>>n>>m;        memset(mp,0,sizeof(mp));        for(int i=0;i
         
        
       
      

 

。

注意是 n - 最大匹配  不是2n