P8186 [USACO22FEB] Redistributing Gifts S 题解

· · 题解

题意简述

题目描述的是农夫约翰有 N 个标记为 1 \dotsm N 的礼物，要分给 N 头同样标记为 1 \dotsm N 的奶牛。每头奶牛都有一个愿望单，是一个 1 \dotsm N 的排列，表示奶牛对礼物的偏好顺序，越早出现的礼物越喜欢。农夫约翰懒惰地将 i 号礼物直接分配给了 i 号奶牛。现在奶牛们决定重新分配礼物，使得每头奶牛都能得到原礼物或更喜欢的礼物。要求计算对于每个 i（1 \le i \le N），重新分配后 i 号奶牛可能得到的最好的礼物。

解题思路

不难想到建图，每个奶牛和可以得到的礼物连边。

考虑贪心，对于每个奶牛 i 依次枚举礼物 a _ {i,j}，判断剩下的奶牛和礼物能不能分配成功。显然，分配成功的充要条件是剩余的奶牛和礼物是二分图的完美匹配。时间复杂度 O(n^5)。

注意到，使用匈牙利算法匹配左部点 i 时，会依次枚举每一条与之相连的边并检查对应的右部点 j 是否能和 i 形成匹配，这本质上就是一个贪心的过程。所以，对于每个奶牛 i，只需连边时按喜欢程度从大到小依次连边，在匹配所有奶牛和礼物时最后一个匹配这个奶牛 i，就可以在匈牙利算法中完成贪心。时间复杂度 O(n^4)。

考虑优化，不难发现若对每个奶牛 i 都跑一个二分图匹配，会有很多重复计算。不妨先把整个图先匹配好，枚举到奶牛 i 时再将 i 所对应的匹配删除，对其重新匹配。时间复杂度降为 O(n^3)，可以通过本题。

显然，该二分图必然存在完美匹配，因为将所有奶牛 i 和礼物 i 匹配就是完美匹配。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500;
vector<int> edge[N+2];
int p[N+2],q[N+2];
bool vis[N+2];
bool match(int x){
    for(int i:edge[x]) if(!vis[i]){
        vis[i]=1;
        if(p[i]==0||match(p[i])){
            p[i]=x;
            q[x]=i;
            return 1;
        }
    }
    return 0;
}
int main(){
    // freopen("data.in","r",stdin);
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        bool flag=1;
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            if(flag){
                edge[i].push_back(x);
            }
            if(x==i){
                flag=0;
            }
        }
    }
    //二分图匹配？
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        match(i);
    }
    for(int i=1;i<=n;i++){
        q[i]=p[q[i]]=0;
        memset(vis,0,sizeof vis);
        match(i);
        cout<<q[i]<<"\n";
    }
    // cout<<"\n";
    return 0;
}