| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
发个模板,给大家参考参考。#include<iostream>
#include<stdio.h>
using namespace std;
int mat[200][200];
int cx[200],cy[200];
int mk[200];
int nx,ny=84;
int path(int u)
{
int v;
for(v=0;v<ny;v++)//B集合顶定点个数
{
if(mat[u][v]&&!mk[v])// u和v相邻,且没有访问过
{
mk[v]=1;//标记访问v
//如果v没有匹配,或者v已经匹配了,但从cy[v]出发可以找到一条增广路
//注意如果前一个条件成立,则不会递归调用。
if(cy[v]==-1||path(cy[v]))
{
cx[u]=v;//把v匹配给u
cy[v]=u;//把u匹配给v
return 1;//找到可增广路
}
}
}
return 0;//不存在,从u出发的增广路
}
void MaxMatch()
{
int res=0;//所求的的最大匹配值
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
int i;
for(i=0;i<nx;i++)//X集合顶定点个数,n个
{
if(cx[i]==-1)//从每个未覆盖点出发进行寻找增广路
{
memset(mk,0,sizeof(mk));
res+=path(i);
}
}
cout<<res<<endl;
}
int main()
{
while(scanf("%d",&nx)!=EOF)
{
memset(mat,0,sizeof(mat));
int i;
int u,p,q;
for(i=0;i<nx;i++)
{
scanf("%d",&u);
while(u--)
{
scanf("%d %d",&p,&q);
mat[i][(p-1)*12+q-1]=1;
}
}
MaxMatch();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator