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