這道題 就是利用匈牙利算法 然后將問題轉化為 最大匹配問題 view plaincopy to clipboardprint?
#include <iostream>
const int MaxN = 500 + 1;
bool map[MaxN][MaxN] , ck[MaxN];
int n , match[MaxN] , max_match , k;
bool search(int x)
{
int i , t;
for (i = 1 ; i <= n ; i ++)
if (map[i][x]&&!ck[i])
{
ck[i] = true;
t = match[i];
match[i] = x;
if (t ==0 || search(t)) return true;
match[i] = t;
}
return false;
}
void hungary()
{
int i ;
memset(match , 0 , sizeof(match));
max_match = 0;
for ( i = 1 ; i <= n ; i ++)
{
memset(ck , false , sizeof(ck));
if (search(i)) max_match++;
}
}
int main()
{
int i , x , y;
scanf("%d%d",&n,&k);
for ( i = 1 ; i <= k ; i++)
{
scanf("%d%d",&x,&y);
map[x][y] = true;
}
hungary();
printf("%d\n",max_match);
return 0;
}
#include <iostream>
const int MaxN = 500 + 1;
bool map[MaxN][MaxN] , ck[MaxN];
int n , match[MaxN] , max_match , k;
bool search(int x)
{
int i , t;
for (i = 1 ; i <= n ; i ++)
if (map[i][x]&&!ck[i])
{
ck[i] = true;
t = match[i];
match[i] = x;
if (t ==0 || search(t)) return true;
match[i] = t;
}
return false;
}
void hungary()
{
int i ;
memset(match , 0 , sizeof(match));
max_match = 0;
for ( i = 1 ; i <= n ; i ++)
{
memset(ck , false , sizeof(ck));
if (search(i)) max_match++;
}
}
int main()
{
int i , x , y;
scanf("%d%d",&n,&k);
for ( i = 1 ; i <= k ; i++)
{
scanf("%d%d",&x,&y);
map[x][y] = true;
}
hungary();
printf("%d\n",max_match);
return 0;
}
完全是 模板的套用 呵呵
posted on 2009-08-04 17:05
付翔 閱讀(939)
評論(0) 編輯 收藏 引用