荒野聚餐

题意

有 $2n$ 位鸟人参与聚餐，其中 $n$ 位是雄性鸟人，$n$ 位是雌性鸟人。第 $i$ 位雄性鸟人和第 $j$ 位雌性鸟人的亲和度是 $a_{i,j}$。

神速鸟人要为这 $2n$ 位鸟人分配经费，满足任意一对雌雄鸟人被分配的经费总和大于它们的亲和度。除此之外，神速鸟人还可以选择在音乐设备上的开销 $S$，使得每一对鸟人对经费的要求都降低 $\dfrac{S}{C}$。

对多个不同的 $C$，求出分配的最少经费。

解析

写出题目的线性规划形式

$$\min f = \sum_{i=1}^nx_i+\sum_{i=1}^ny_i+S\\ s.t.\forall i, j:x_i+y_j+\dfrac{S}{C}\ge a_{i,j}$$

它的对偶线性规划是

$$\max f^\prime=\sum_{i=1}^n\sum_{j=1}^nx_{i,j}a_{i,j}\\ s.t.\begin{cases} \forall i:\sum\limits_{j=1}^n x_{i,j}\le 1\\ \forall i:\sum\limits_{j=1}^n x_{j,i}\le 1\\ \sum\limits_{i=1}^n\sum\limits_{j=1}^mx_{i,j}\le C \end{cases}$$

这一对对偶线性规划正是 KM 算法中顶标和相等子图的关系！

不难发现，这正是二分图限制匹配数为 $C$ 的最大权匹配。由于这个问题可以视作一个容量为整数的最小费用最大流问题，它一定存在一个最优解为整数解 (题面中所谓保证答案最后一位不是 $4$ 或 $5$ 实际上是在蒙人)。

使用 KM 算法即可在 $O(n^3)$ 的时间复杂度内解决。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 5e2 + 19;

int n, q;

namespace km{

int q[maxn], h, t;
int w[maxn][maxn], mx[maxn], my[maxn], pre[maxn], sla[maxn], lx[maxn], ly[maxn];
bool vist_x[maxn], vist_y[maxn];

bool check(int node){
    vist_y[node] = true;
    if(my[node]){
        q[++t] = my[node], vist_x[my[node]] = true;
        return false;
    }

    while(node){
        my[node] = pre[node];
        std::swap(mx[pre[node]], node);
    }
    return true;
}

void bfs(void){ 
    std::fill(vist_x + 1, vist_x + 1 + n, false);
    std::fill(vist_y + 1, vist_y + 1 + n, false);
    std::fill(sla + 1, sla + 1 + n, 2e9);

    h = 1, t = 0;
    for(int i = 1; i <= n; ++i)
        if(!mx[i])
            q[++t] = i, vist_x[i] = true;

    while(true){
        while(h <= t){
            int node = q[h++];
            for(int i = 1; i <= n; ++i)
                if(!vist_y[i]){
                    int d = lx[node] + ly[i] - w[node][i];
                    if(d <= sla[i]){
                        pre[i] = node;
                        if(d) sla[i] = d;
                        else if(check(i)) return;
                    }
                }
        }

        int a = 2e9;
        for(int i = 1; i <= n; ++i)
            if(!vist_y[i])
                a = std::min(a, sla[i]);

        for(int i = 1; i <= n; ++i){
            if(vist_x[i]) lx[i] -= a;
            if(vist_y[i]) ly[i] += a;
            else sla[i] -= a;
        }

        for(int i = 1; i <= n; ++i)
            if(!vist_y[i] && !sla[i] && check(i))
                return;
    }
}

}

ll ans[maxn];
int T;

int main(){
    std::scanf("%d", &T);
    std::scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            std::scanf("%d", km::w[i] + j);

    std::fill(km::lx + 1, km::lx + n + 1, 1e9);
    for(int i = 1; i <= n; ++i){
        km::bfs();
        for(int j = 1; j <= n; ++j)
            if(km::mx[j])
                ans[i] += km::w[j][km::mx[j]];
    }

    while(q--){
        static int c;
        std::scanf("%d", &c);
        std::printf("%lld.0\n", ans[std::min(n, c)]);
    }

    return 0;
}

来源

NOI.AC #2011 荒野聚餐

评论