简单的二分图匹配：
每一个位置的数可能边成那些数连边即可
Game with Pearls
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 122 Accepted Submission(s): 85
1) Tom and Jerry come up together with a number K.
2) Tom provides N tubes. Within each tube, there are several pearls. The number of pearls in each tube is at least 1 and at most N.
3) Jerry puts some more pearls into each tube. The number of pearls put into each tube has to be either 0 or a positive multiple of K. After that Jerry organizes these tubes in the order that the first tube has exact one pearl, the 2nd tube has exact 2 pearls,
…, the Nth tube has exact N pearls.
4) If Jerry succeeds, he wins the game, otherwise Tom wins.
Write a program to determine who wins the game according to a given N, K and initial number of pearls in each tube. If Tom wins the game, output “Tom”, otherwise, output “Jerry”.
2 5 1 1 2 3 4 5 6 2 1 2 3 4 5 5
Jerry Tom
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110;
int n,K;
struct Edge
{
int to,next;
}edge[maxn*maxn];
int Adj[maxn],Size;
void init()
{
memset(Adj,-1,sizeof(Adj)); Size=0;
}
void add_edge(int u,int v)
{
edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++;
}
int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(!used[v])
{
used[v]=true;
if(linker[v]==-1||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int res=0;
memset(linker,-1,sizeof(linker));
for(int u=1;u<=n;u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int a[maxn];
int main()
{
int T_T;
scanf("%d",&T_T);
while(T_T--)
{
scanf("%d%d",&n,&K);
init();
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
for(int j=0;a[i]+j*K<=n;j++)
{
int v=a[i]+j*K;
add_edge(i,v);
}
}
int pp=hungary();
//cout<<"pp: "<<pp<<endl;
if(pp==n) puts("Jerry");
else puts("Tom");
}
return 0;
}