[POJ] 1325 Machine Schedule(最小点覆盖)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[POJ] 1325 Machine Schedule(最小点覆盖)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1580字，纯文字阅读大概需要3分钟。
内容图文
题目地址：http://poj.org/problem?id=1325
给出一系列任务，每个任务用三元组(i,x,y)表示，代表任务i可以在机器A的x模式，或者在机器B的y模式下完成。机器A和B每切换一次模式需要重启一次。问完成这些任务，最少需要重启机器多少次？
关于(i,x,y)，从机器A的x向机器B的y连边，则问题就转变成了最小顶点覆盖问题。因为二分图最小顶点覆盖数=最大匹配数，所以求一下最大匹配就可以了。
1 #include<cstdio>
2 #include<iostream>
3 #include<string.h>
4 #include<algorithm>
5 #include<math.h>
6 #include<stdbool.h>
7 #include<time.h>
8 #include<stdlib.h>
9 #include<set>
10 #include<map>
11 #include<stack>
12 #include<queue>
13 #include<vector>
14usingnamespace std;
15#define clr(x,y) memset(x,y,sizeof(x))
16#define sqr(x) ((x)*(x))
17#define rep(i,a,b) for(int i=(a);i<=(b);i++)
18#define LL long long
19#define INF 0x3f3f3f3f
20#define A first
21#define B second
22#define PI 3.14159265358979323
23constint N=100+11;
24int n,m,f[N],g[N][N],link[N];
2526void init()
27{
28 clr(f,0);
29 clr(g,0);
30 clr(link,-1);
31}
3233bool find(int x)
34{
35for(int i=1;i<=m;i++) {
36if(!f[i] && g[x][i]) {
37 f[i]=1;
38if(link[i]==-1 || find(link[i])) {
39 link[i]=x;
40returntrue;
41 }
42 }
43 }
4445returnfalse;
46}
4748int hungary()
49{
50int ans=0;
51for(int i=1;i<=n;i++) {
52 clr(f,0);
53if(find(i)) ans++;
54 }
55return ans;
56}
5758int main()
59{
60int u,v,num,k;
6162while(~scanf("%d",&n)) {
63if(!n) break;
64 init();
65 scanf("%d%d",&m,&k);
66while(k--) {
67 scanf("%d%d%d",&num,&u,&v);
68 g[u][v]=1;
69 }
70 printf("%d\n",hungary());
71 }
7273return0;
74 }
原文：http://www.cnblogs.com/sxiszero/p/4375643.html
内容总结
以上是互联网集市为您收集整理的[POJ] 1325 Machine Schedule(最小点覆盖)全部内容，希望文章能够帮你解决[POJ] 1325 Machine Schedule(最小点覆盖)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。