今天开始一天一道算法题的博客
今天的题是最大独立集,
对于最大独立集,本质上是求最大匹配,
对于这题,我们只要把不满足条件的人连起来,那么就构成了一张二分图,求好匹配以后,记得除以2,因为匈牙利算法在求匹配的时候,是从i=0到i=n-1的,这里是全部的点,所以相当于算了2次,
//烧死那对异性恋
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 505
struct edge
{
int to,next;
}mat[maxn];
int num,head[maxn*3],n;
char sex[maxn][1];
int high[maxn];
char stycle[maxn][10......
阅读全文