HDOJ 1150 Machine Schedule 二分匹配

本文主要是介绍HDOJ 1150 Machine Schedule 二分匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模型建立：机器A的n个状态表示成X集合中得n个点，机器B的m个状态表示成Y集合的m个点。当一个任务可以用机器A的i状态，和机器B的j状态解决的时候，我们连接X集合中的第i个结点和Y集合中的第j个结点。所有的任务都完成意味着所有的边都被选择到。因此这个题就变成求最小覆盖点集，即最大匹配数。注意，我们不考虑能用机器A或机器B的0状态来解决的任务，因为这样的任务一开始就都被解决了。

#include<iostream>   
using namespace std;  
const int MAX = 102;  
bool linkMap[MAX][MAX];  
int  crossPath[MAX];  
bool used[MAX];  
int n, m;  
bool search(int u)  
{  for (int i=1;i<m;i++)  {  if (linkMap[u][i]&&!used[i])  {  used[i]=1;//保证路径上无重复点出现   if (crossPath[i]==-1||search(crossPath[i]))  {  crossPath[i]=u;//①增广路径的取反   return true;  }  }  }  return false;  
}  int hungary()  
{  int cnt = 0;   memset(crossPath, -1, sizeof(crossPath));  for(int i= 1; i<n; i++)  {  memset(used,0, sizeof(used));  if(search(i))   cnt++;  }  return cnt;  
}  
int main()  
{  //ifstream cin("Machine Schedule.txt");   int k;  while(cin>>n,n)  {  cin>>m>>k;  memset(linkMap,false, sizeof(linkMap));    for(int i =0; i < k; i++)   {   int v1, v2;      cin>>v1>>v1>>v2;  if(v1&&v2)  linkMap[v1][v2] = true;    }  cout<<hungary()<<endl;  }  return 0;  
}

这篇关于HDOJ 1150 Machine Schedule 二分匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---