钱宝贪婪洞窟帐号共享:ACM二分图匹配 HDU2063
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2063
摘录于互联网,原创作者redraiment,很详细的二分图匹配入门资料!
#include
#include
#include
#include
using namespace std;
typedef struct node
{
int ord;
node * next;
}Node;
const int size = 512 + 1;
Node list[size];
int X[size];
int Y[size];
bool visit[size];
int size_x;
int size_y;
stack
void init()
{
int i;
for (i = 1; i <= size_x; i++)
list[i].next = NULL;
memset(X, 0, (size_x + 1) * sizeof(int));
memset(Y, 0, (size_y + 1) * sizeof(int));
}
void input(int len)
{
int i;
int x;
int y;
Node* p;
for (i = 0; i < len; i++)
{
scanf("%d%d", &x, &y);
p = new Node;
p->ord = y;
p->next = list[x].next;
list[x].next = p;
}
}
bool dfs(int x)
{
Node* p;
stk.push(x);
for (p = list[x].next; p; p = p->next)
{
if (!visit[p->ord])
{
visit[p->ord] = true;
stk.push(p->ord);
if (!Y[p->ord] || dfs(Y[p->ord]))
return true;
else
stk.pop();
}
}
stk.pop();
return false;
}
void solve()
{
int i;
int top;
for (i = 1; i <= size_x; i++)
{
while (!stk.empty()) stk.pop();
memset(visit, false, size_y + 1);
if (dfs(i))
{
while (!stk.empty())
{
top = stk.top();
stk.pop();
Y[top] = stk.top();
X[stk.top()] = top;
stk.pop();
}
}
}
}
void output()
{
int i;
int count = 0;
Node* p;
for (i = 1; i <= size_x; i++)
{
if (X[i]) count++;
while (p = list[i].next)
{
list[i].next = p->next;
delete p;
}
}
cout << count << endl;
}
int main(void)
{
int n;
while (scanf("%d", &n), n)
{
scanf("%d%d", &size_x, &size_y);
init();
input(n);
solve();
output();
while (!stk.empty()) stk.pop();
}
return 0;
}