POJ-1274 The Perfect Stall
1279 ワード
タイトルリンク:http://poj.org/problem?id=1274
テーマ:
n頭牛とm個の牛小屋があって、今牛は乳を産みますが、すべての牛は自分の好きな牛小屋でしか乳を産みません.最も多くの産乳量を求めます.
問題解決の考え方:
二分図の最大マッチング.
隣接行列が実現し、map[i][j]=1は、乳牛iがj牛小屋で乳を産むのが好きであることを表し、牛小屋を遍歴し、牛がここで乳を産むのが好きであれば、その牛をマークします.
その後、乳牛を遍歴し、マークが一致する牛小屋を表すと、乳を産むことができ、一致した乳牛の個数を統計すると最大一致数になります.
コードは次のとおりです.
テーマ:
n頭牛とm個の牛小屋があって、今牛は乳を産みますが、すべての牛は自分の好きな牛小屋でしか乳を産みません.最も多くの産乳量を求めます.
問題解決の考え方:
二分図の最大マッチング.
隣接行列が実現し、map[i][j]=1は、乳牛iがj牛小屋で乳を産むのが好きであることを表し、牛小屋を遍歴し、牛がここで乳を産むのが好きであれば、その牛をマークします.
その後、乳牛を遍歴し、マークが一致する牛小屋を表すと、乳を産むことができ、一致した乳牛の個数を統計すると最大一致数になります.
コードは次のとおりです.
#include<cstdio>
#include<cstring>
using namespace std;
#define N 510
int n, m;
int map[N][N];
int match[N];
bool use[N];
bool find(int u)
{
for(int i = 1; i <= m; ++i) // ,
{
if(!use[i] && map[u][i])
{
use[i] = true;
if(match[i] == -1 || find(match[i]))
{
match[i] = u;
return true;
}
}
}
return false;
}
int sum()
{
int sumall = 0;
for(int i = 1; i <= n; ++i) //
{
memset(use, false, sizeof(use));
if(find(i))
sumall++;
}
return sumall;
}
int main()
{
int allnum, u;
while(scanf("%d%d", &n, &m) != EOF)
{
memset(map, 0, sizeof(map));
memset(match, -1, sizeof(match));
for(int i = 1; i <= n; ++i)
{
scanf("%d", &allnum);
for(int j = 1; j <= allnum; ++j)
{
scanf("%d", &u);
map[i][u] = 1; //
}
}
printf("%d
", sum());
}
return 0;
}