hdu多校第八场 1011 （hdu6667） Roundgod and Milk Tea 二分图匹配

题意：

有若干个班，每个班有些人要喝奶茶，也提供一些奶茶，一人喝一杯，但是自己班的人不能喝自己班的奶茶，求最多能有多少人喝上奶茶。

题解：

典型的二分图匹配问题，学生在左，奶茶在右，学生和非自己班的奶茶连边。

因为班级数1e6,每个班级有1e9个奶茶或学生，直接按照上述建边跑匈牙利算法会T

考虑霍尔结婚定理：点集S，点集T，边集E，其中E中的边所连两点一点在S中，一点在T中，如果S中的k个点各自经过E与T中k个不同的点相连，则称形成了一个大小为k的匹配。

k=|S|则称为完美匹配

对于S的任意子集W，如果|W|<=|Ng(W)| <==> S有完美匹配。

其中Ng(W)为点集T中所有与W相邻(neighbor)的结点的集合。

必要性(<=)显然。

充分性(=>)...还不会，要用数学归纳法，先挖个坑。

推论：

最大匹配为对于任意S的子集W

|S|-max(|W|-|Ng(W)|)

证明不难，找一个满足霍尔定理完美匹配要求的S的子集，踢开剩下的点，就是一个完美匹配。

我们去找那个让 (|W|-|Ng(W)|)最大化的W'

对于此题，只有如下三种情况：

1，W'为空，此时所有学生都能喝到奶茶。

2，W'只包含一个班的学生，那么Ng(w)就一定是其他班的奶茶，W'想最大化必然包括这个班所有学生

3，W'包含了多个班的学生，那么Ng(w)就一定是所有的奶茶，同理，W'想最大化，必须包括所有学生，此时有多少奶茶就有多少人喝。

具体执行步骤如下：

逐个遍历班级，维护非此班级的奶茶数，检查此班同学人数是否大于非此班奶茶数。

出现0次这种情况，答案为总人数

每出现一次这种情况，答案记为原答案和总人数-此班人数+非此班奶茶数的较小值

最后检查总奶茶数是否更小。

#include <bits/stdc++.h>

#define LL long long

using namespace std;

int n;

LL a[], b[];

int main() {

    int T; scanf("%d", &T);

    while (T--) {

        scanf("%d", &n);

        for (int i = ; i < n; i++) scanf("%lld%lld", a + i, b + i);

        LL totu = accumulate(a, a + n, 0ll);

        LL totv = accumulate(b, b + n, 0ll);

        LL ans;

        int flag=;

        for (int i = ; i < n; i++) {

            if(a[i]>totv-b[i]){

                ans=totu-a[i]+totv-b[i];

                flag++;

            }

        }

        if(flag==){

            ans=totu;

        }

        ans=min(ans,totv);

        printf("%lld\n", ans);

    }

    return ;

}

巴特西

hdu多校第八场 1011 （hdu6667） Roundgod and Milk Tea 二分图匹配

最新文章

热门文章