题意：给出n个人的信息，名字、特征、排名。
在排名相差2的前提下，特征为testdata可以与特征为statements的组队，特征为anything可以任何一人组队；
求最多匹配对数，并将每队名字输出；
思路：将排名%4，结果小于2的一组，大于等于2的一组，则同一组中不会匹配，以此构建二分图；二分图匹配；
匈牙利算法的思想是：
左点集与右点集匹配：
1）有匹配的先匹配；
2）后来匹配的如果与前面的匹配冲突，前面的匹配重新匹配，如果匹配成功了，则加上新匹配；否则新匹配不成立；
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int link[5050],vis[5050]; int n,m,h; int match[5055][5050],rk[5050]; char name[5050][505],str[505][5050]; int left[5050],right[5050],sta[5050]; int dfs(int x) { int i; for(i=1;i<=m;i++) { if(!vis[i]&&match[x][i]) { vis[i]=1; if(link[i]==-1||dfs(link[i])) { link[i]=x; return 1; } } } return 0; } int hungary() { int sum=0,j; memset(link,-1,sizeof(link)); for(j=1;j<=h;j++) { memset(vis,0,sizeof(vis)); if(dfs(j)) sum++; } return sum; } int main() { int i,j,k,res; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) { scanf("%s%s%d",name[i],str[i],&rk[i]); if(strcmp(str[i],"anything")==0) sta[i]=3; else if(strcmp(str[i],"statements")==0) sta[i]=1; else sta[i]=2; } h=m=0; for(i=1;i<=n;i++) { if(rk[i]%4<2) left[++h]=i; else right[++m]=i; } memset(match,0,sizeof(match)); for(i=1;i<=h;i++) { for(j=1;j<=m;j++) { if((sta[left[i]]==3||sta[right[j]]==3)||abs(rk[left[i]-rk[right[j]]])==2) match[i][j]=1; } } res=hungary(); printf("%d ",res); for(i=1;i<=m;i++) { if(~link[i]) { int num1=left[link[i]]; int num2=right[i]; if(sta[num1]==2) swap(num1,num2); if(sta[num2]==1) swap(num1,num2); printf("%s %s ",name[num1],name[num2]); } } } return 0; }