LA3415保守的老师

题意：

有n个学生，老师要带他们出去玩，但是老师比较保守，怕他们之间萌生爱意，所以带出去的所有同学必须至少满足四个条件中的一组，问最多能带多少人出去玩。

思路：

比较简单二分图的最大独立集元素个数，我们直接把可能产生爱意（四个都不满足）的连上边，然后一遍匈牙利，最后输出n-匹配数就行了，为什么是这样我就不证明了，比较经典简单的问题。

#include<stdio.h>

#include<string.h>

#define N_node 550

#define N_edge 255000

typedef struct

{

int to ,next;

}STAR;

typedef struct

{

int h;

char str1[5] ,str2[110] ,str3[110];

}NODE;

NODE node[N_node];

STAR E[N_edge];

int list[N_node] ,tot;

int mk_dfs[N_node] ,mk_gx[N_node];

void add(int a, int b)

{

E[++tot].to = b;

E[tot].next = list[a];

list[a] = tot;

}

int DFS_XYL(int x)

{

for(int k = list[x] ;k ;k = E[k].next)

{

int to = E[k].to;

if(mk_dfs[to]) continue;

mk_dfs[to] = 1;

if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))

{

mk_gx[to] = x;

return 1;

}

}

return 0;

}

int abss(int x)

{

return x > 0 ? x : -x;

}

bool jude(int a ,int b)

{

return abss(node[a].h - node[b].h) <= 40 && node[a].str1[0] != node[b].str1[0] && !strcmp(node[a].str2 ,node[b].str2) && strcmp(node[a].str3 ,node[b].str3);

}

int main ()

{

int t ,n ,i ,j;

scanf("%d" ,&t);

while(t--)

{

scanf("%d" ,&n);

for(i = 1 ;i <= n ;i ++)

scanf("%d %s %s %s" ,&node[i].h ,node[i].str1 ,node[i].str2 ,node[i].str3);

memset(list ,0 ,sizeof(list)) ,tot = 1;

for(i = 1 ;i <= n ;i ++)

for(j = i + 1 ;j <= n ;j ++)

{

if(jude(i ,j))

{

node[i].str1[0] == 'M' ? add(i ,j) : add(j ,i);

}

}

memset(mk_gx ,255 ,sizeof(mk_gx));

int Ans = 0;

for(i = 1 ;i <= n ;i ++)

{

memset(mk_dfs ,0 ,sizeof(mk_dfs));

Ans += DFS_XYL(i);

}

printf("%d\n" ,n - Ans);

}

return 0;

}

巴特西

LA3415保守的老师

最新文章

热门文章