本文主要是介绍二分图匹配---- 二分的真谛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
有三种角色，假设是a,b,c; 其中a是攻，b是受,c可攻可受，每个人都除了拥有一个角色外，还有一个属性值，只有两个绝对值相差2的攻,受才能配成一对，
问最多能配成多少对
如果按角色来分肯定不行, 那么要用二分图的话,就是对属性值来分 左右两边 分别是 %4<2 和%4>=2 这样正好二分。。。这个思想很重要。。我也是后来才明白的
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define LL long long
#define N 1007
#define pi acos(-1.0)
using namespace std;
vector<int> p[N];
bool vis[N];
int mat[N];
bool find(int x){for(int i=0;i<p[x].size();++i){int y=p[x][i];if(vis[y]) continue;vis[y]=true;if(mat[y]==0||find(mat[y])){mat[y]=x;return true;}} return false;
}
char name[N][25];
int state[N];
int value[N];
int main(){int n;int i,j;char s[25];scanf("%d",&n);for(i=1;i<=n;++i){scanf("%s%s%d",name[i],s,&value[i]);if(*s=='a') state[i]=1;//state[]表示角色1是可攻可受else if(*s=='s') state[i]=2;else state[i]=3;for(j=1;j<i;++j) if(abs(value[i]-value[j])==2)if(state[i]==1||state[j]==1||state[i]!=state[j]){if(value[i]%4<2) p[i].push_back(j); //二分图建图;;左边放%4<2 右边连线%4>=2else p[j].push_back(i);}}int ans=0;for(i=1;i<=n;++i)if(value[i]%4<2){memset(vis,false,sizeof(vis));if(find(i)) ans++;}printf("%d\n",ans);for(i=1;i<=n;++i)if(mat[i]){if(state[i]==2||state[mat[i]]==3)printf("%s %s\n",name[i],name[mat[i]]);else printf("%s %s\n",name[mat[i]],name[i]);}return 0;
}
这篇关于二分图匹配---- 二分的真谛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
