ZJUT1321-Dividing//MAXMATCH

2306 단어 inputeachMatrixoutput
Dividing Time Limit:1000MS  Memory Limit:32768K

Description:

There are N(N is an even number) people in ZJUT. each person in ZJUT, loves some ones and hates the others. Is it possible to divide them to N/2 groups in which the two people love each other?
 

Input:

The first line gives a number T, means the number of test cases. The first line of each test case gives a number N, and then follows a N*N matrix. The elements of the matrix are either 0 or 1. If the j-th number in the i-th row is 1, it means the i-th person loves the j-th person, else he doesn’t love him. N,T <= 16

Output:

If it is possible to divide them, print “Yes”, else print “No”.

Sample Input:

2
4
1 1 1 0
1 1 0 1
1 1 1 0
0 1 0 1
4
1 1 0 0
0 1 0 1
1 0 1 0
0 0 1 1

Sample Output:

Yes
No

Source:

lily
이것은 내가 본 것 중 가장 느린 OJ다...
구도가 일치하는 조건에 주의하고 서로 좋아해야 한다. 그림은 대칭적이지 않다
#include
#include
int n;
bool mat[20][20],used[20];
int link[20];
bool can(int t)
{
    for(int i=1;i<=n;i++)
    if(used[i]==false&&mat[t][i]&&mat[i][t])
    {
        used[i]=true;
        if(link[i]==-1||can(link[i]))
        {
            link[i]=t;
            return true;
        }
    }
    return false;
}
int MaxMatch()
{
    int num=0;
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        if(can(i)) num++;
    }
    return num;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
          {
              int x;
              scanf("%d",&x);
              if(i!=j) mat[i][j]=x; else mat[i][j]=0;
          }
        if(MaxMatch()==n) printf("Yes/n");
        else printf("No/n");
    }
    return 0;
}

좋은 웹페이지 즐겨찾기