> #include<stdio.h>
> #include<iostream.h>
> #include<string.h>
> int map[1005][1005];
> int chk[1005];
> int match[1005];
> int result,m,n;
> int dfs(int p) 
> { 
>   int i,t; 
>   for(i=0;i<n;i++) 
>     if((map[p][i]==1) && (chk[i]==0)) 
>     { 
>        chk[i]=1; 
>        t=match[i]; 
>        match[i]=p; 
>        if(t==-1||dfs(t)) 
>           return 1; 
>        match[i]=t; 
>      } 
>   return 0; 
> } 
> int check() 
> { 
>   int i,res=0; 
>   memset(match,-1,sizeof(match));
>   for(i=0;i<m;i++) 
>   { 
>     memset(chk,0,sizeof(chk));
>     if(dfs(i)==1) res++; 
>   } 
>   return res; 
> } 
> 
> int main()
> {
>     int c;
>     scanf("%d",&c);
>     while(c--)
>     {
>         scanf("%d%d",&m,&n);
>         int i,j,k;
>         for(i=0;i<m;i++)
>           for(j=0;j<n;j++)
>             map[i][j]=0;
>         for(i=0;i<n;i++)
>         {
>                 int a,b;
>                 scanf("%d%d",&a,&b);
>                 map[a-1][i]=1;
>                 map[b-1][i]=1;
>         }  
>        result=check();
>         //for(i=0;i<n;i++)
>          //printf("%d ",match[i]);
>           //printf("\n");
>         if(result==m)
>         {
>             int i;
>             for(i=0;i<n-1;i++) 
>             cout<<match[i]+1<<" ";
>             cout<<match[n-1]+1<<endl;
>         }  
>         else cout<<"NO"<<endl;
>     }
>     return 0;             
> }    
> /*
> 20
> 4 4
> 2 4
> 3 4
> 1 3
> 1 4
> 5 5
> 1 5
> 2 4
> 3 4
> 2 4
> 2 3
> */
> 

• Re:Help ,自己顶一下!!!! (0) ecjtubaowp 2007-05-09 22:18:48