题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1150
/*大致题意: 有两台机器A和B以及k个需要运行的任务。每台机器有n,m种不同的模式,而每个任务都恰好能在一台机器上运行。 机器A上有模式 mode_0, mode_1, …, mode_n-1,机器B上有模式: mode_0, mode_1, … , mode_m-1。 开始的工作模式都是mode_0。每个任务有对应的运行模式,(i, x, y)表示i任务对应的A B机器上的运行模式mode_x, mode_y。 每台机器上的任务可以按照任意顺序执行,但是每台机器每转换一次模式需要重启一次。 请合理为每个任务安排一台机器并合理安排顺序,使得机器重启次数尽量少。并求其值。 */ /* 每个任务要有对应A B机器的模式中至少要有一种来运行,问题转化为,求二分图中最少的点(模式)使得每个边(模式对应的任务)至少和其中的一个点覆盖。 也就是二分图最小顶点覆盖问题 */ #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 main() { 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;//连接左右两边 } int count = 0; memset(crossPath, -1, sizeof(crossPath)); for(int i= 1; i<n; i++) { memset(used, 0, sizeof(used)); if(search(i)) //查找增广路径 count ++; } cout<< count <<endl; } return 0; }