//zory 【Poj1325】Machine Schedule | Zory的个人博客

【Poj1325】Machine Schedule

来源和评测点

Beijing 2002
Poj1325

题目

【题目大意】
有两部机器A和B。
A机器有n种工作模式0,1,2,3,……n-1,总共n种。
B机器有m种工作模式0,1,2,3,……m-1,总共m种。
有k个任务,每个任务可以在 A机器的某个模式 或者 B机器的某个模式中完成。
A和B机器开始时都默认在0模式,要选择其他模式就要重启一次。
求完成k个任务至少需要重启多少次机器。最后以0结束。输出最少重启机器的次数。
【输入格式】
第一行三个整数n,m,k(0

分析

请先仔细看题,然后思考。

其实数据的输入形式很多时候就给出了提示,
例如这道题中,每个任务与A、B分别有两个可能,与点、边之间的关系非常像。
而要求最少的重启机器次数,显然最好能一个模式做多几个任务,使用过的模式数量之和就是答案。
而机器只有两个,又可以联想到二分图匹配。

综上所述,构图如下:
把A、B看作两个集合,模式看作点,任务看作边,每个任务连接两个点,
最后通过匈牙利算法计算出最大匹配对数,根据定理得到最小点覆盖。

不过……这题目是卡邻接表的么?TLE了
改成邻接矩阵就0ms了
怀疑数据有超级多重边。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=100,MAXM=1000;
//*******************全局定义*******************
/*struct pt
{
int hou;
}p[2*MAXN];
struct rod
{
int y,g;
}e[MAXM];*/
//*******************实现*******************
/*int ln;
void ins(int x,int y)
{
ln++;
e[ln].y=y;
e[ln].g=p[x].hou;
p[x].hou=ln;
}*/
//*******************接口*******************
int n,m,k;
int ask[MAXN];
int match[MAXN];
bool mp[MAXN][MAXN];
int t;
bool findmuniu(int x)
{
//for(int k=p[x].hou;k>0;k=e[k].g)
for(int i=1;i<=m;i++)
{
if(mp[x][i]==0) continue;
//int i=e[k].y;
if(ask[i]<t)
{
ask[i]=t;
if(match[i]==0 or findmuniu(match[i]))
//C++中的or逻辑关系,左边true则不会执行右边的语句
{
match[i]=x;
return 1;
}
}
}
return 0;
}
//*******************主函数*******************
int main()
{
while(scanf("%d",&n) and n!=0)
{
memset(ask,0,sizeof(ask));
memset(match,0,sizeof(match));
//ln=0;for(int i=1;i<=n+m;i++) p[i].hou=0;
memset(mp,0,sizeof(mp));
scanf("%d%d",&m,&k);
for(int i=1;i<=k;i++)
{
int t,a,b;
scanf("%d%d%d",&t,&a,&b);
//ins(a,n+b);
mp[a][b]=1;
}
int ans=0;
for(t=1;t<=n;t++) ans+=findmuniu(t);
printf("%d\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-01/Machine_Schedule.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!