题意：给n个人，每个人都有3个参数，分别是名字，能做的事(a:statements b:testdate a、b都可以:anything)，Rank
要求：一个人只能做一个事件，要两个人Rank相差2才能共同做a、b，问最多能做多少个a、b，并输出 做a人的名字 做b人的名字
很明显是二分匹配 稳定婚姻问题。
一开始按照 能做a的人->能做b的人 建图 怎么都过不了案例。。。
后来发现若是这样建图，对于
1 ab 4
2 a 2
3 b 6
若是这样建图 
那么就会有两个匹配：1和3 以及 2和1
为什么不是一个匹配呢？
因为对于稳定婚姻而言 男的 女的 都分别有编号为1到n的人
因此1和3 以及 2和1的含义 (若用这样的建图 用稳定婚姻来解释的话 就是) 1号男人和3号女人 以及 2号男人以及1号女人 <这样看来确实两对>
而对于这个题目 很显然 男女是共用一个编号的
若是按a->b这样建图 实际上来说 并没有“二分”
那么要怎么建图呢？
此题一共就俩限制一个是a->b，另一个是Rank之差为2。那么既然不是前一个，那必定是后一个咯~
所以二分的方法就是：
Rank相差2的不能在同一个集合里
比如Rank为2的为男 那么Rank为4的就要是女的 Rank为6的为男 那么Rank为8的就要是女
那这样分的话 要是规定Rank 6为女(即限制了4为男)， 若之前已经规定了Rank 2为男(即限制了4为女) 那不就矛盾了吗？
于是先按照Rank来排个序 再来确定男女两个集合就没问题了~
给一个案例：
6 a anything 2 b anything 4 c anything 4 d anything 4 e anything 6 f anything 6
代码：(因为是比赛中写的 所以巨丑...)
1 #include <bits/stdc++.h> 2 using namespace std; 3 struct node 4 { 5 string name; 6 bool a, b; 7 int Rank; 8 }a[5005]; 9 bool cmp(node a, node b) 10 { 11 return a.Rank<b.Rank; 12 } 13 vector<int> v[5005]; 14 int lef[5005]; 15 bool t[5005]; 16 int n; 17 int fa[5005]; 18 bool match(int x) 19 { 20 for(int i=0;i<(int)v[x].size();i++) 21 if(t[v[x][i]]==0) 22 { 23 t[v[x][i]]=1; 24 if(lef[v[x][i]]==-1 || match(lef[v[x][i]])) 25 { 26 fa[x]=-1, fa[fa[x]]=-1; 27 fa[v[x][i]]=x, fa[x]=v[x][i]; 28 lef[v[x][i]]=x; 29 return true; 30 } 31 } 32 return false; 33 } 34 int solve() 35 { 36 int ans=0; 37 memset(lef, -1, sizeof(lef)); 38 memset(fa, -1, sizeof(fa)); 39 for(int i=1;i<=n;i++) 40 if(v[i].size()) 41 { 42 memset(t, 0, sizeof(t)); 43 if(match(i)) 44 ans++; 45 } 46 return ans; 47 } 48 bool vis[5005]; 49 bool zz[5005]; 50 int main() 51 { 52 scanf("%d", &n); 53 for(int i=1;i<=n;i++) 54 { 55 string s; 56 cin>>a[i].name>>s; 57 if(s=="anything") 58 a[i].a=1, a[i].b=1; 59 else if(s=="statements") 60 a[i].a=1, a[i].b=0; 61 else 62 a[i].a=0, a[i].b=1; 63 scanf("%d", &a[i].Rank); 64 } 65 for(int i=0;i<=n;i++) 66 v[i].clear(); 67 sort(a+1, a+n+1, cmp); 68 memset(zz, 0, sizeof(zz)); 69 for(int i=1;i<=n;i++) 70 { 71 if(zz[a[i].Rank-2]) 72 continue; 73 zz[a[i].Rank]=1; 74 } 75 for(int i=1;i<=n;i++) 76 for(int j=i+1;j<=n;j++) 77 if(abs(a[i].Rank-a[j].Rank)==2) 78 if((a[i].a==1 && a[j].b==1) || (a[i].b==1 && a[j].a==1)) 79 { 80 if(zz[a[i].Rank]) 81 v[i].push_back(j); 82 else if(zz[a[j].Rank]) 83 v[j].push_back(i); 84 } 85 printf("%d ", solve()); 86 memset(vis, 0, sizeof(vis)); 87 for(int i=1;i<=n;i++) 88 if(fa[i]!=-1 && fa[fa[i]]==i && !vis[i] && !vis[fa[i]]) 89 { 90 if(a[i].b==1 && a[fa[i]].a==1) 91 cout<<a[fa[i]].name<<" "<<a[i].name<<endl; 92 else 93 cout<<a[i].name<<" "<<a[fa[i]].name<<endl; 94 vis[i]=1, vis[fa[i]]=1; 95 } 96 return 0; 97 }