[0,m)种工作模式,现在K个工作要完成,每个工作能由任一台机器的某个模式完成 刚开始两台机器都工作在0模式(这句话很重要
起看漏了这句 悲剧了一下 = =。。。) 每切换一种模式都要重起机器,现要重新分配K个工作完成顺序,使得机器重起时间最少。
思路:这题很容易想到二分图的最小点覆盖 要注意的一定的是
//208K
47MS
#include <stdio.h>
#include <string.h>
#define M 105
int n,m,k,mat[M][M];
int link[M],vis[M];
bool DFS (int u)
{
0;v < m;v ++)
if (!vis[v]&&mat[u][v])
{
vis[v] = 1;
if (link[v] == -1||DFS(link[v]))
{
link[v] = u;
return true;
}
}
false;
}
int MaxMatch ()
{
0;
(link,0xff,sizeof(link));
< n;u ++)
memset (vis,0,sizeof(vis));
if (DFS(u))
res ++;
res;
}
int main ()
{
i,u,v;
("%d",&n)&&n)
scanf ("%d%d",&m,&k);
memset (mat,0,sizeof(mat));
while (k --)
{
scanf
("%d%d%d",&i,&u,&v);
if (u*v !=
0)
//0模式不加边
mat[u][v] = 1;
}
printf ("%d\n",MaxMatch());