hdu 1150 Machine Schedule

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

中心思想 转化为二分图最小顶点覆盖问题。

二分图最小顶点覆盖数=二分图最大匹配数

那么二分图到底是哪两部分呢？ 一部分是机器A ，一部分是机器B，
如果某个任务，可由 A 的Xi 和 B 的 Yi模式完成。则在Xi 和 Yi之间连一条线，有向图，A—>B 。
所以 二分图左部分集合就是机器A的模式的集合，右部分是机器B模式集合。模式从1 开始，排除模式为0的元素。

详细参考博客：http://blog.csdn.net/loy_184548/article/details/51956121

二分图最大匹配：匈牙利算法模板

bool dfs(int v){for(vector<int>::iterator it=g[v].begin()it!=g[v].end();it++){if(!visited[*it]){visited[*it]=true;if(matched[*it]==-1||dfs(matched[*it])){matched[*it]=v;return true;}}}return false;
}
int hungarian(){int num=0;for(int i=1;i<=m;i++){matched[i]=-1;}for(int i=1;i<=n;i++){memset(visited,false,sizeof(visited));if(dfs(i))num++;}return num;
}

完整AC代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>using namespace std;const int maxn=105;bool visited[maxn];int matched[maxn];vector<int> g[maxn];
int n,m,k;bool dfs(int v){for(vector<int>::iterator it=g[v].begin();it!=g[v].end();it++){if(!visited[*it]){visited[*it]=true;if(matched[*it]==-1||dfs(matched[*it])){matched[*it]=v;return true;}}}return false;}int hungarian(){int num=0;for(int i=1;i<=m;i++){matched[i]=-1;}for(int i=1;i<=n;i++){memset(visited,false,sizeof(visited));if(dfs(i))num++;}return num;}int main()
{int tmp;int ans;while(scanf("%d",&n)){if(n==0)break;scanf("%d%d",&m,&k);int a,b;for(int i=1;i<=n;i++) g[i].clear();for(int i=0;i<k;i++){scanf("%d",&tmp);//uselessscanf("%d%d",&a,&b);if(a==0&&b==0) continue;g[a].push_back(b);}ans=hungarian();printf("%d\n",ans);;}return 0;
}

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

---