【最大匹配】‘组队难题’

Description
一年一度的保研杯又开始了,重庆游戏与电子竞技大学的同学们都跃跃欲试。今年学校收集了参赛学生的信息,打算统一分配队伍。学校把学生分为端茶、倒水和大佬三种类型,一个队伍由三个学生组成,而且不能同时有多个端茶学生或者多个倒水学生。大佬比较佛系,不会和其他学生起冲突,但是剩下两种学生都是凡人,所以一些学生之间会有矛盾。现在问题来了,在避免矛盾的前提下,最多能组成多少只队伍呢?
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个整数,学生数量N(1<=N<=300)和矛盾数量M(0<=M<=90000)。学生的编号从1到N。 接下来的N行,每行包括一个字符串,第i行的字符串表示i号学生的类型:”DL”表示大佬,”DC”表示端茶,”DS”表示倒水。 接下来的M行,每行包括两个正整数,表示有矛盾的学生的编号。保证矛盾双方编号不同。 数据保证矛盾不会和”DL”类型的同学有关,保证每对同学的矛盾最多只会出现一次。
Output
输出一个整数,表示最多能组成的队伍数量。
Sample Input
4 2
DL
DC
DC
DS
2 4
3 4
Sample Output

虽然一眼就看出来是最大匹配,但是有个坑点没有注意到。

一个队不能有多个端茶送水但是可以有多个大佬…………………………

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int dl=0;
int d[303]={0};
vector<int> qds,qdc;
int cp[303][303]={0};
int vis[303]={0};
int mch[303]={0};
int fbfs(int x)
{
	int j;
	for(int k=0;k<qdc.size();k++)
	{
		j=qdc[k];
		if(cp[x][j]==1 && vis[j]==0)
		{
			vis[j]=1;
			if(mch[j]==0 || fbfs(mch[j]))
			{
				mch[j]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		char s[5];	
		scanf("%s",s+1);
		if(s[2]=='L') dl++;
		if(s[2]=='S') 
		{
			d[i]=1;
			qds.push_back(i);
		}
		if(s[2]=='C')
		{
			d[i]=2;
			qdc.push_back(i);
		}
	}
	for(int i=0;i<qds.size();i++)
	for(int j=0;j<qdc.size();j++)
	{
		cp[qdc[j]][qds[i]]=1;
		cp[qds[i]][qdc[j]]=1;
	}
	for(int i=1;i<=m;i++)
	{
		int s,t;
		scanf("%d%d",&s,&t);
		if(d[s]==d[t]) continue;
		cp[s][t]=0;
		cp[t][s]=0;
	}
	int all=0;
	for(int i=0;i<qds.size();i++)
	{
		memset(vis,0,sizeof(vis));
		if(fbfs(qds[i])) all++;
	} 
	if(dl<=all) ans=dl;
	else
	{
		ans=all;
		int a=qdc.size()-all;
		int b=qds.size()-all;
		dl-=all;
		while(dl>=2)
		{
			if(a>=1) 
			{
				a-=1;
				dl-=2;
				ans++;
				continue;
			}
			if(b>=1)
			{
				b-=1;
				dl-=2;
				ans++;
				continue;
			}
			if(dl>=3)
			{
				dl-=3;
				ans++;
				continue;
			}
			break;
		}		 
	}
	printf("%d",ans);
} 

 

发表评论