POJ2239 Selecting Courses(二分图最大匹配)

题目链接

N节课,每节课在一个星期中的某一节,求最多能选几节课

好吧,想了半天没想出来,最后看了题解是二分图最大匹配,好弱

建图: 每节课 与 时间有一条边

 #include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = + ;
int vis[N], Left[N];
vector<int> g[N];
int n;
bool mach(int u)
{
int Size = g[u].size();
for (int i = ; i < Size; i++)
{
int v = g[u][i];
if (!vis[v])
{
vis[v] = ;
if (Left[v] == - || mach(Left[v]))
{
Left[v] = u;
return true;
}
}
}
return false;
}
int main()
{
while (scanf("%d", &n) != EOF)
{
int t, p, q;
for (int i = ; i <= n; i++)
g[i].clear();
for (int i = ; i <= n; i++)
{
scanf("%d", &t);
for (int j = ; j <= t; j++)
{
scanf("%d%d", &p, &q);
g[i].push_back(p * + q); // 可以将每一节转化成一个整数
}
}
memset(Left, -, sizeof(Left));
int ans = ;
for (int i = ; i <= n; i++)
{
memset(vis, , sizeof(vis));
if (mach(i))
ans++;
}
printf("%d\n", ans);
}
return ;
}
上一篇:DRBD+Heartbeat实现自动切换


下一篇:虚树------sdoi2011<消耗战>