?? 1466_girls and boys.cpp
字號:
/*
最小頂點覆蓋 = 最大匹配
本題求n --> n的最小頂點覆蓋的補集
即男女生兩兩之間沒有曖昧關系的最大集合
*/
#include"memory.h"
#include"stdio.h"
#define L_MAX 501
#define R_MAX 501
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 i,j,k;int r;
while(scanf("%d",&l_num) != EOF)
{ r_num = l_num;
memset(array,0,sizeof array);
for(i = 0;i < l_num;i++){
scanf("%d: (%d)",&j,&r);
while(r--)
{ scanf(" %d",&k);
array[j][k] = 1;
}
}
printf("%d\n",r_num - hungary()/2);//hungary必為偶數
}
return 1;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -