HDU-1151-AirRaid(最小路径覆盖)-白红宇

HDU-1151-AirRaid(最小路径覆盖)

阅读量：7169 次

发布时间：2019-06-29

本文共 1280 字，大约阅读时间需要 4 分钟。

链接：

题意:

一个城镇有n个路口，由一些单向马路连接。现在要安排一些伞兵降落在某些路口上，清查所有的路口。一个伞兵可以沿着马路一路清查过去。清查过程中不能有两个伞兵同时清查一个路口（应该是为了防止暴露）。给定城镇的线路，求最少需要几个人伞兵就能清查所有的路口。

思路：

最小路径覆盖:

首先将每个节点分成两个，有一条有向边l-r，则在图上有l到r为1 。

同时对拆分成两个结点的图进行二分图匹配。

因为每匹配一条边，证明有一个点被加到了一条路径上，则节点总数减去最大匹配数就是最小路径。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;typedef long long LL;const int MAXN = 2000+10;vector
                    
                      G[MAXN];int Link[MAXN], Vis[MAXN];int n, m;void Init(){ for (int i = 1;i <= n;i++) G[i].clear();}bool Dfs(int x){ for (int i = 0;i < G[x].size();i++) { int node = G[x][i]; if (Vis[node]) continue; Vis[node] = 1; if (Link[node] == -1 || Dfs(Link[node])) { Link[node] = x; return true; } } return false;}int Solve(){ memset(Link, -1, sizeof(Link)); int cnt = 0; for (int i = 1;i <= n;i++) { memset(Vis, 0, sizeof(Vis)); if (Dfs(i)) cnt++; } return cnt;}int main(){ int t; cin >> t; while (t--) { cin >> n >> m; Init(); int l, r; for (int i = 1;i <= m;i++) { cin >> l >> r; G[l].push_back(r); } int cnt = Solve(); cout << n - cnt << endl; } return 0;}

转载于:https://www.cnblogs.com/YDDDD/p/10869452.html

你可能感兴趣的文章