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 |
怎么这个样子就给AC了呢,代码贴下,小小的纪念下。。。对所谓的二分匹配多了那么一丁点儿的认识 ,,,,当时构了一个错误的图, 百度后看了别人的构图法, 才给A了。。还是匈牙利算法,直接套模板的,就是构图会存在一定的难度。。。。。 跑了2000多MS,汗,汗,,,,.... #include<stdio.h> #include<stdlib.h> #include<string.h> #define arr 501 int N,map[arr][arr],pre[arr]; bool used[arr]; bool find(int x) { int i; for(i=1;i<=N;i++) { if(!used[i]&&map[x][i]) { used[i]=1; if(pre[i]==-1||find(pre[i])) { pre[i]=x; return 1; } } } return 0; } int MMG() { int i,count=0; memset(pre,-1,sizeof(pre)); for(i=1;i<=N;i++) { memset(used,0,sizeof(used)); if(find(i)) count++; } return count; } int main() { int i,num,order,j,t; char a,b,c,str[300]; while(scanf("%d",&N)!=EOF) { /*n=N/2; if(N%2==1) n++; m=N-n; //构图,n个点去匹配m个点;*/ memset(map,0,sizeof(map)); for(i=1;i<=N;i++) { scanf("%d",&order); scanf("%c%c%c",&a,&b,&c); scanf("%d",&num); //cin>>M>>c>>c>>m>>c即可; //printf("num=%d\n",num); scanf("%c%c",&a,&b); for(j=1;j<=num;j++) { scanf("%d",&t); map[i][t]=1; //printf("map[%d][%d]=1\n",i,t-n+1); } } /*for(j=1;j<=m;j++) gets(str); //scanf("%s");开始用了这个一直错,汗,汗。。 */ int ans=MMG(); if(ans%2==1) ans+=1; printf("%d\n",N-ans/2);//最大独立集点数=N-最大匹配数 ; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator