題意：
? ? ? 女生和男生之間只要滿足四個條件中的一個，那么兩個人就不會在一起！然后給出一些男生和女生，問最多多少人一起做活動彼此不會產生曖昧關系。


思路：
? ? ? 這樣的問題還是比較裸的問法，就是再問最大獨立集元素個數，左邊是男，右邊是女，建立二分圖，然后可能曖昧的連接在一起，最后n-最大匹配數，就行了，還有就是很多人都不是很理解這個結論為什么是對的，我說下我的簡單理解，我們可以這樣想，分成兩個集合，這兩個集合之間的最大曖昧關系我們只要刪除產生曖昧關系的兩個人其中的一個（這個不是隨意刪除誰，要看當時情況，但是肯定可以刪除其中一個人）這樣最后剩下的就沒有辦法在組成曖昧關系了，如果還不理解想想二分匹配匈牙利算法的過程，匹配完之后剩下的已經沒有辦法在匹配了，那么剩下的肯定是獨立的，然后在在匹配里面選擇一半拿出來（不是隨意現則），可以有方法做到剩下的一半與之前匹配剩下的都是獨立的，這樣答案就是n-匹配數.


#include<stdio.h>
#include<string.h>


#define N_node 500 + 50
#define N_edge 500 * 500 + 50


typedef struct
{
? ? int a;
? ? char b[5];
? ? char c[105];
? ? char d[105];
}NODE;


typedef struct
{
? ? int to ,next;
}STAR;


NODE node[N_node];
STAR E[N_edge];
int list[N_node] ,tot;
int mkdfs[N_node] ,mkgx[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(mkdfs[to]) continue;
? ? ? ? mkdfs[to] = 1;
? ? ? ? if(mkgx[to] == -1 || DFS_XYL(mkgx[to]))
? ? ? ? {
? ? ? ? ? ? mkgx[to] = x;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? }
? ? return 0;
}


int abss(int x)
{
? ? return x > 0 ? x : -x;
}


int main ()
{
? ? int i ,j ,t ,n;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d" ,&n);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d %s %s %s" ,&node[i].a ,node[i].b ,node[i].c ,node[i].d);
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? if(node[i].b[0] != 'M') continue;
? ? ? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(node[j].b[0] == 'M') continue;
? ? ? ? ? ? ? ? if(abss(node[i].a - node[j].a) > 40) continue;
? ? ? ? ? ? ? ? if(strcmp(node[i].c ,node[j].c)) continue;
? ? ? ? ? ? ? ? if(!strcmp(node[i].d ,node[j].d)) continue;
? ? ? ? ? ? ? ? add(i ,j);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? memset(mkgx ,255 ,sizeof(mkgx));
? ? ? ? int ans = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? memset(mkdfs ,0 ,sizeof(mkdfs));
? ? ? ? ? ? ans += DFS_XYL(i);
? ? ? ? }
? ? ? ? printf("%d\n" ,n - ans);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ2771最大独立集元素个数的全部內容，希望文章能夠幫你解決所遇到的問題。

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