#include <cstdio>
#include <iostream>
using namespace std;
bool map[1005][1005];
int chk[1005];
int match[1005];
int result,m,n;
int Dfs(int p) 
{ 
  int i,t; 
  for(i=0;i<m;i++) 
    if((map[i][p]==1) && (chk[i]==0)) 
    { 
       chk[i]=1; 
       t=match[i]; 
       match[i]=p; 
       if((t==-1 )||( Dfs(t)==1)) 
          return 1; 
       match[i]=t; 
     } 
  return 0; 
} 

int pro() 
{ 
  int i,res=0; 
  for(i=0;i<n;i++) 
  { 
    for(int j=0;j<m;j++)
     chk[j]=0; 
    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<m;i++)
           match[i]=-1;

        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=pro();//匈牙利匹配
        int temp[1005];
        for(i=0;i<n;i++)
          temp[i]=0;
        if(result==n)
        {
            int i;
            for(i=0;i<m;i++)
            {
                if(match[i]>=0) temp[match[i]]=i;//转换match到另一边
            }    
            for(i=0;i<n-1;i++) 
              cout<<temp[i]+1<<" ";
            cout<<temp[n-1]+1<<endl;
        }  
        else cout<<"NO"<<endl;
    }
    return 0;             
        
}    

• 难道一行可以射多个点？ (1654) tengshengbo 2005-08-08 23:44:00
  • result==n这个有问题 (0) sunmoonstar_love 2005-08-08 23:59:36
  • result==r，然后剩下的 c-r个，直接打出来 (0) sunmoonstar_love 2005-08-09 00:01:16
    • 嗯，刚过，就是这样，咱们开始理解题意有误 (0) sunmoonstar_love 2005-08-09 00:08:16
    • 后面剩下的应该是去该列的任意一个白格子所在的行就可以了吧，怎么还老是ＷＡ？？ (0) huicpc16 2005-08-24 21:38:18
  • 多谢，我改改看 (0) tengshengbo 2005-08-09 00:08:45
  • Re:难道一行可以射多个点？ (0) tengshengbo 2005-08-09 00:15:59
  • 这题到什么意思？实在读不懂了。帮忙解答一下。 (0) tengshengbo 2005-08-09 00:18:57
    • 每一行看，至少有一个白格，从每一列看，有且仅有一个白格被射中，也就是说为每一行匹配一个列，其余的列随意指定 (0) sunmoonstar_love 2005-08-09 00:21:00
      • 过了。原来如此。理解错题了。 (0) tengshengbo 2005-08-09 00:23:53
• 陷進了無限的 WA 中...算法該沒有問題的，CEOI '97 的 test data 都過了 (1509) hkho5 2006-09-23 18:31:50