Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

发个模板,给大家参考参考。

Posted by 1108000126 at 2012-08-08 20:53:32 on Problem 2239
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator