HDU5090--Game with Pearls 二分图匹配 （匈牙利算法）

题意：给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,1,1+n)
        cin>>a[i];
        sort(a+1,a+1+n);
        int ok = -1,i=1;
        while(i<=n)
        {
            if(a[i]>i)
            {
                ok = 1;
                break;
            }
            else if(a[i]<i)
            {
                a[i]+=k;
                sort(a+1,a+1+n);
                continue;
            }
            else
                i++;
        }
        if(ok==1)
            cout<<"Tom
";
        else
            cout<<"Jerry
";
    }
    return 0;
}

带权值的二分图匹配(改编下列某大神的代码)：

///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 = 1 ; v <= n ; v++ ) ///考虑所有 Yi 顶点 v
    {
        if(g[u][v]&&!vis[v]) ///v 与 u 邻接，且没有访问过
        {
            vis[v] = 1;///如果 v 没有匹配，或者 v 已经匹配了，但从 march[v]出发可以找到一条增广路
            if(march[v] == -1 || dfs(march[v])) ///注意如果前一个条件成立，则不会递归调用
            {
                march[v] = u; ///把 v 匹配给 u
                return 1; ///找到可增广路
            }
        }
    }
    mat[u] = 0;///如果不存在从u出发的增广路
    return 0 ;
}

void MaxMatch( ) ///求二部图最大匹配的匈牙利算法
{
    int res = 0; ///所求得的最大匹配
    for(int i = 1 ; i <= n ; i++)
    {
        memset(vis , 0 , sizeof(vis)) ;
        int u = p[i].v;///按照排好的权值一个个寻找匹配点
        res += dfs(u);
    }
    ///res是能够匹配的个数
    repu(i,1,n+1)
    {
        int t = march[i];///在dfs中是把v匹配给u，因此需要进一步转化
        mat[t] = i;
    }
    for(int i = 1; i < 1+n; i++)
        if(i==1)
            printf("%d", mat[i]);
        else
            printf(" %d", mat[i]);
}
int main()
{
    int a,b,m;
    scanf("%d",&n);
    memset(g,0,sizeof(g));
    memset(march,-1,sizeof(march));
    memset(mat,0,sizeof(mat));
    repu(i,1,1+n)
    {
        scanf("%d",&a);
        p[i].val = a;
        p[i].v = i;
    }
    sort(p+1,p+1+n);///按照权值排序
    repu(i,1,1+n)
    {
        scanf("%d",&m);
        repu(j,0,m)
        {
            scanf("%d",&b);
            g[i][b] = 1;
        }
    }
    MaxMatch();
    return 0;
}

二分图匹配的代码(某个大神的代码，先留着)：

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[110][310]; ///邻接矩阵，true代表有边相连
bool flag,visit[310];    ///记录V2中的某个点是否被搜索过
int match[310];   ///记录与V2中的点匹配的点的编号
int p,n;   ///二分图中左边、右边集合中顶点的数目

/// 匈牙利算法
bool dfs(int u)
{
    for (int i = 1; i <= n; ++i)
    {
        if (g[u][i] && !visit[i])   ///如果节点i与u相邻并且未被查找过
        {
            visit[i] = true;   ///标记i为已查找过
            if (match[i] == -1 || 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 = 1; i <= p; i++)
        {
            for (j = 1; j <= n; j++)
                g[i][j] = false;
        }
        for (i = 1; i <= n; i++)
            match[i] = -1;
        flag = true;
        for (i = 1; i <= p; i++)
        {
            scanf("%d",&k);
            if (k == 0)
                flag = false;
            while (k--)
            {
                scanf("%d",&v);
                g[i][v]  = true;
            }
        }
        if (flag)
        {
            ans = 0;
            for (i = 1; 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 0;
}