HDU-1150-MachineSchedule(二分图匹配)-白红宇

HDU-1150-MachineSchedule(二分图匹配)

阅读量：5743 次

发布时间：2019-06-18

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

链接：

题意：

在一个工厂，有两台机器A,

B生产产品。A机器有n种工作模式（模式0,模式1....模式n-1）。

B机器有m种工作模式（模式0,模式1....模式m-1）。

现在要加工k个产品。每个产品可以由两台机器特定的模式生产。

例如：产品0，可以由A机器在3号模式或B机器4号模式生产。

两台机器初始模式都在模式0，但是，这两台机器不是很先进，如果需要切换模式，只能由

人手工切换模式，手工切换可以切换到任意模式。求加工完k个产品需要切换模式的最少次数。

（生产产品的顺序可以任意）

思路：

二分图匹配，尽力从1找到n-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 = 1e3+10;vector
                    
                      G[MAXN];int Link[MAXN], Vis[MAXN];int n, m, k;bool Dfs(int x){ for (int i = 0;i < G[x].size();i++) { int node = G[x][i]; if (!Vis[node]) { Vis[node] = 1; if (Link[node] == 0 || Dfs(Link[node])) { Link[node] = x; return true; } } } return false;}int Solve(){ int res = 0; memset(Link, 0, sizeof(Link)); for (int i = 1;i < n;i++) { memset(Vis, 0, sizeof(Vis)); if (Dfs(i)) res++; } return res;}void Init(){ for (int i = 1;i <= n;i++) G[i].clear();}int main(){ while (cin >> n && n) {Init(); cin >> m >> k; int num, l, r; for (int i = 1;i <= k;i++) { cin >> num >> l >> r; if (l > 0 && r > 0) G[l].push_back(r); } cout << Solve() << endl; } return 0;}

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

你可能感兴趣的文章