Machine Schedule Asia 2002, Beijing (Mainland China)
Machine Schedule
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4309 Accepted Submission(s): 2102
Problem Description
As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.
There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, …, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.
Input
The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.
The input will be terminated by a line containing a single zero.
Output
The output should be one integer per line, which means the minimal times of restarting machine.
Sample Input
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
Sample Output
3
Source
Asia 2002, Beijing (Mainland China)
题意：
早上想了一个早上，才理解为什么。。下午，学长看我无聊就给我一个了据说是书记花钱买来的多校联赛的账号。 可是坑爹的终于看到了清华北大的被宁波中学的给虐了。。但话说自己也给虐的不行。。。看到了原来实力相差是如此的大啊，，，，
话说被虐是正常的，没有人生来是大牛或大神，所以该做的题还是继续做吧。。。。
该题主要考查二分图的最小覆盖，可以证明的：最小覆盖 == 最大匹配 ； 不要问我why，I don't know!!!!!! 记得高数老师说过当你一直都想证明某个问题时，你有一天会发现你是无法证明的，因为总有一个是原始起点。扯远了。。。 该结论还是要牢记的，因为后面的很多公式将都会根据这个公式推导出。
说一说该题的题意吧，就是告诉你有两个机器，且这两个机器可以分别用不同的档位对不同的工作进行工作。且每更换一次，需要重启一次，问你怎么用最少的次数。可以从中清晰的想到是典型的二分匹配问题。因为两个机器是没有关系的，但我当时也没理解为什么会那样，郁闷了一个早上，哈哈，突然想去了，书记说过的，搞ACM的就是在不断郁闷中成长的，看来果然是哈！！！。
言归正传，因为每一次给你一件工作你都有两个选择，可以选择A Or B 但每一步的选择都会影响着后来的结果，因此，当我们求出了最大的匹配数时候，就说明要独立的换挡工作的个数是多少（试想，一个点只能匹配一个点的模型）。
#include <stdio.h>
#include <string.h>
#define CL(x,v);memset(x,v,sizeof(x));
const int MAX = 1002;
int n,m,link[102];
bool used[102],graph[MAX][MAX];
bool Find(int u)
{
for(int v = 1;v <= m;v++)
if(!used[v]&&graph[u][v])
{
used[v] = 1;
if(link[v] == -1||Find(link[v]))
{
link[v] = u;
return true;
}
}
return false;
}
int KM()
{
int res = 0;
CL(link,-1);
for(int i = 1;i <= n;i++)
{
CL(used,0);
if(Find(i)) res++;
}
return res;
}
int main()
{
int i,a,b,index,k;
while(scanf("%d",&n),n)
{
CL(graph,0);
scanf("%d%d",&m,&k);
for(i = 0;i < k;i++)
{
scanf("%d%d%d",&index,&a,&b);
graph[a][b] = 1;
}
printf("%d\n",KM());
}
return 0;
}
#include <stdio.h>
#include <string.h>
#define CL(x,v);memset(x,v,sizeof(x));
const int MAX = 1002;
int n,m,link[102];
bool used[102],graph[MAX][MAX];
bool Find(int u)
{
for(int v = 1;v <= m;v++)
if(!used[v]&&graph[u][v])
{
used[v] = 1;
if(link[v] == -1||Find(link[v]))
{
link[v] = u;
return true;
}
}
return false;
}
int KM()
{
int res = 0;
CL(link,-1);
for(int i = 1;i <= n;i++)
{
CL(used,0);
if(Find(i)) res++;
}
return res;
}
int main()
{
int i,a,b,index,k;
while(scanf("%d",&n),n)
{
CL(graph,0);
scanf("%d%d",&m,&k);
for(i = 0;i < k;i++)
{
scanf("%d%d%d",&index,&a,&b);
graph[a][b] = 1;
}
printf("%d\n",KM());
}
return 0;
}
补充：综合编程 , 其他综合 ,
