http://poj.org/problem?id=1466
题意:从n个男女同学中找出两两没有任何关系的最大人数。
使用C++输入输出,WA了好几次,改了用C就过,也不知道怎么回事,好气愤啊!!!
Sample Input
7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0
Sample Output
5 2
Source Code
#include <iostream>
using namespace std;
const int N = 600;
int pic[N][N],flag[N],link[N];
bool find(int x){
int j;
for(int i=1;i<=pic[x][0];i++){
j=pic[x][i];
if(!flag[j]){
flag[j]=1;
if(link[j]==-1 || find(link[j])){
link[j]=x;
return true;
}
}
}
return false;
}
int main(){
int n,i,j,x,ans;
while(scanf("%d",&n)!=EOF){
memset(pic,0,sizeof pic);
for(i=0;i<n;i++){
link[i]=-1;
}
for(i=0;i<n;i++){
scanf("%d: ",&x);
scanf("(%d)",&pic[x][0]);
if(!pic[x][0]) continue;
for(j=1;j<=pic[x][0];j++){
scanf("%d",&pic[x][j]);
}
}
ans=0;
for(i=0;i<n;i++){
memset(flag,0,sizeof flag);
if(find(i))
ans++;
}
printf("%d\n",n-ans/2);
}
return 0;
}
转载于:https://www.cnblogs.com/pcwl/archive/2011/04/27/2030989.html