題意：
? ? ? 有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保守的老师的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。