kamailio 相关问题记录

Description

Input

Output

Sample Input

2
4
35 M classicism programming
0 M baroque skiing
43 M baroque chess
30 F baroque soccer
8
27 M romance programming
194 F baroque programming
67 M baroque ping-pong
51 M classicism programming
80 M classicism Paintball
35 M baroque ping-pong
39 F romance ping-pong
110 M romance Paintball

Sample Output

3
7

Source

//1500K	1172MS
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 507
int link[M],g[M][M];
bool vis[M];
int n;
struct ST
{
    int height;
    char sex[2],music[107],sport[107];
}pupils[M];
bool judge(int x,int y)
{
    if(fabs(pupils[x].height-pupils[y].height)>40||strcmp(pupils[x].sex,pupils[y].sex)==0||strcmp(pupils[x].music,pupils[y].music)!=0||strcmp(pupils[x].sport,pupils[y].sport)==0)
        return false;
    return true;
}
bool find(int i)
{
    for(int j=1;j<=n;j++)
        if(!vis[j]&&g[i][j])
        {
            vis[j]=true;
            if(!link[j]||find(link[j]))
            {
                link[j]=i;
                return true;
            }
        }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(link,0,sizeof(link));
        memset(g,0,sizeof(g));
        int count=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%s%s%s",&pupils[i].height,pupils[i].sex,pupils[i].music,pupils[i].sport);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(judge(i,j))g[i][j]=1;
        for(int i=1;i<=n;i++)
        {
            memset(vis,false,sizeof(vis));
            if(find(i))count++;
        }
        printf("%d\n",n-count/2);
    }
    return 0;
}