题意：给N个容器，每个容器里有一定数目的珍珠，现在Jerry开始在管子上面再放一些珍珠，放上的珍珠数必须是K的倍数，可以不放。最后将容器排序，如果可以做到第i个容器上面有i个珍珠，则Jerry胜出，反之Tom胜出。
思路：数据比较小，所以我是水过的，模拟过程 + 贪心就能过。但正解是二分图匹配，之前没接触过。
二分图匹配：解释一下第二组样例，k = 2;
从左向右，每一个能够匹配 i 的（a），就去掉 i 周围其他的边，然后再也去掉a能指向的边，计算一下共有几个能匹配的，如果是n，则Jerry胜，否则Tom胜；
水过的代码
///水过的代码
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <algorithm>
#define Max 2147483647
#define INF 0x7fffffff
#define N 90010
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define repu(i, a, b) for(int i = (a); i < (b); i++)
const double PI=-acos(-1.0);
using namespace std;
int a[N];
int main()
{
int n,T,k;
cin>>T;
while(T--)
{
cin>>n>>k;
repu(i,,+n)
cin>>a[i];
sort(a+,a++n);
int ok = -,i=;
while(i<=n)
{
if(a[i]>i)
{
ok = ;
break;
}
else if(a[i]<i)
{
a[i]+=k;
sort(a+,a++n);
continue;
}
else
i++;
}
if(ok==)
cout<<"Tom\n";
else
cout<<"Jerry\n";
}
return ;
}
带权值的二分图匹配(改编下列某大神的代码)：
///http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82360#problem/B
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <algorithm>
#define Max 2147483647
#define INF 0x7fffffff
#define N 901
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define repu(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
int g[N][N],vis[N],march[N],mat[N];
int n;
struct S
{
int val,v;
bool operator < (const S& s ) const
{
return val > s.val;
}
} p[N];
int dfs( int u )
{
for( int v = ; v <= n ; v++ ) ///考虑所有 Yi 顶点 v
{
if(g[u][v]&&!vis[v]) ///v 与 u 邻接，且没有访问过
{
vis[v] = ;///如果 v 没有匹配，或者 v 已经匹配了，但从 march[v]出发可以找到一条增广路
if(march[v] == - || dfs(march[v])) ///注意如果前一个条件成立，则不会递归调用
{
march[v] = u; ///把 v 匹配给 u
return ; ///找到可增广路
}
}
}
mat[u] = ;///如果不存在从u出发的增广路
return ;
} void MaxMatch( ) ///求二部图最大匹配的匈牙利算法
{
int res = ; ///所求得的最大匹配
for(int i = ; i <= n ; i++)
{
memset(vis , , sizeof(vis)) ;
int u = p[i].v;///按照排好的权值一个个寻找匹配点
res += dfs(u);
}
///res是能够匹配的个数
repu(i,,n+)
{
int t = march[i];///在dfs中是把v匹配给u，因此需要进一步转化
mat[t] = i;
}
for(int i = ; i < +n; i++)
if(i==)
printf("%d", mat[i]);
else
printf(" %d", mat[i]);
}
int main()
{
int a,b,m;
scanf("%d",&n);
memset(g,,sizeof(g));
memset(march,-,sizeof(march));
memset(mat,,sizeof(mat));
repu(i,,+n)
{
scanf("%d",&a);
p[i].val = a;
p[i].v = i;
}
sort(p+,p++n);///按照权值排序
repu(i,,+n)
{
scanf("%d",&m);
repu(j,,m)
{
scanf("%d",&b);
g[i][b] = ;
}
}
MaxMatch();
return ;
}
二分图匹配的代码(某个大神的代码，先留着)：
POJ1469是一个裸的二分图匹配，有p个课程，n个学生，求是否能让每个课程都有学生。
///转自：http://blog.csdn.net/hackbuteer1/article/details/7398008
/*==================================================*\
| 二分图匹配（匈牙利算法DFS 实现）
| INIT: g[][]邻接矩阵;
| 优点：实现简洁容易理解，适用于稠密图，DFS找增广路快。
| 找一条增广路的复杂度为O（E），最多找V条增广路，故时间复杂度为O（VE）
==================================================*/
#include<stdio.h>
#include<memory.h>
bool g[][]; ///邻接矩阵，true代表有边相连
bool flag,visit[]; ///记录V2中的某个点是否被搜索过
int match[]; ///记录与V2中的点匹配的点的编号
int p,n; ///二分图中左边、右边集合中顶点的数目 /// 匈牙利算法
bool dfs(int u)
{
for (int i = ; i <= n; ++i)
{
if (g[u][i] && !visit[i]) ///如果节点i与u相邻并且未被查找过
{
visit[i] = true; ///标记i为已查找过
if (match[i] == - || dfs(match[i])) ///如果i未在前一个匹配M中，或者i在匹配M中，但是从与i相邻的节点出发可以有增广路径
{
match[i] = u; ///记录查找成功记录，更新匹配M（即“取反”）
return true; ///返回查找成功
}
}
}
return false;
} int main(void)
{
int i,j,k,t,v,ans;
scanf("%d",&t);
while (t--)
{
scanf("%d %d", &p, &n);
for (i = ; i <= p; i++)
{
for (j = ; j <= n; j++)
g[i][j] = false;
}
for (i = ; i <= n; i++)
match[i] = -;
flag = true;
for (i = ; i <= p; i++)
{
scanf("%d",&k);
if (k == )
flag = false;
while (k--)
{
scanf("%d",&v);
g[i][v] = true;
}
}
if (flag)
{
ans = ;
for (i = ; i <= p; i++)
{
memset(visit,false,sizeof(visit)); ///清空上次搜索时的标记
if(dfs(i)) ///从节点i尝试扩展
ans++;
}
if (ans == p)
puts("YES");
else
puts("NO");
}
else
puts("NO");
}
return ;
}
博客讲得很好，很受益