?? 1364_machine schedule.cpp
字號:
/* zju 1364 Machine Schedule
最小頂點覆蓋 = 最大匹配
*/
#include"memory.h"
#include"stdio.h"
#define L_MAX 101
#define R_MAX 101
bool ckd[R_MAX];
int link[R_MAX];
int l_num,r_num;
bool array[L_MAX][R_MAX];
bool augment_path(int t)//找交錯路徑
{
for(int i = 0;i < r_num; i++)
{ if(!ckd[i] && array[t][i]){
ckd[i] = true;
if(link[i] == -1 || augment_path(link[i])){
link[i] = t;
return true;
}
}
}
return false;
}
int hungary()//匈牙利算法
{
memset(link,-1,sizeof link);
int num = 0;
for(int i = 0;i < l_num;i++){
memset(ckd,0,sizeof ckd);
if(augment_path(i)) num++;
}
return num;
}
int main()
{ int k;int f,x,y;
while(scanf("%d%d%d",&l_num,&r_num,&k) != EOF && l_num != 0)
{
memset(array,0,sizeof array);
while(k--)
{
scanf("%d%d%d",&f,&x,&y);
if(x != 0 && y != 0)
array[x][y] = 1;
}
printf("%d\n",hungary());
}
return 1;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -