题解：P11884 [RMI 2024] 拉面 / Ramen

· · 题解

首先考虑如果我们知道了所有的 A_{i,j} 怎么构造最大的方案。

首先我们能说明最优情况下，我们可以用最大权匹配当每个人选拉面的方案。然后人的顺序可以直接拓扑序构造。我们来说明这点。

我们只需要说明每次我们都能选中一个人，他在最大权匹配当中选的是自己最喜欢的拉面。

否则，我们给每个人连一条边，指向抢了他最喜欢的拉面的人。那么这个图没有自环，是一个基环内向树森林。

你发现对一个 \geq 2 的环。每个人都抢了后面的人最喜欢的拉面。这个时候我们肯定可以把所有人的拉面循环位移一下，这样子总和更大了。说明明这并不是最大权匹配。矛盾。因此结论成立。

问题变成了我们怎么去找到我们需要的 A_{i,j} 最后跑最大权匹配呢？

首先我们给每个 A_{i,j} 一个上届 R_{i,j}。每次我们跑一个 R_{i,j} 的最大权匹配出来。然后按照上面构造一个人的顺序 ord。

如果 ord 最终的喜爱度和我们用 R 跑出来的最大权匹配相同。那么就返回 ord，否则我们可以用得到的结果来更新 R。

这样子我们只需要不超过 250 次就能得到结果了

#include<bits/stdc++.h>
// #include"grader.cpp"
using namespace std;
#define ll long long
vector<int> find_order(int N);
vector<pair<int,int>> query(const vector<int>& order);
const int MAXN=2e4+5,inf=1e9;
int e[80][80],p[80],ip[80],chg[80],ex[80],ey[80],slk[80],n;
bool vis[80],used[80];
void match(int u){
    int x,y=0,ty,del;
    p[y]=u;
    memset(slk,0x3f,sizeof(slk));memset(vis,0,sizeof(vis));
    while(1){
        x=p[y];vis[y]=true;del=1e9;ty=0;
        for(int i=1;i<=n;i++) if(!vis[i]){
            if(slk[i]>ex[x]+ey[i]-e[x][i]){
                slk[i]=ex[x]+ey[i]-e[x][i];
                chg[i]=y;
            }
            if(del>slk[i]) del=slk[i],ty=i;
        }
        for(int i=0;i<=n;i++) if(vis[i]){
            ex[p[i]]-=del;ey[i]+=del;
        }else slk[i]-=del;
        y=ty;
        if(!p[y]) break;
    }
    while(y) p[y]=p[chg[y]],y=chg[y];
    return;
} 
ll KM(){
    for(int i=1;i<=n;i++) ex[i]=1e9,ey[i]=chg[i]=p[i]=0;
    for(int i=1;i<=n;i++) match(i);
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=e[p[i]][i],ip[p[i]]=i;
    for(int i=1;i<=n;i++) p[i]=ip[i];
    return ans;
}
inline void chkmin(int &x,int y){if(x>y)x=y;}
vector<int> find_order(int N){
    n=N;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) e[i][j]=inf;
    ll t=0;
    while(1){
        ll E=KM();
        memset(used,0,sizeof(used));memset(vis,0,sizeof(vis));
        vector<int> Q;
        while(1){
            bool flag=false;
            for(int i=1;i<=n;i++) if(!vis[i]){
                bool ok=true;
                for(int j=1;j<=n;j++) if(j!=p[i]) ok&=used[j]||e[i][j]<e[i][p[i]];
                if(ok){vis[i]=used[p[i]]=true;Q.push_back(i);flag=true;}
            }
            if(flag) continue;
            for(int i=1;i<=n;i++) if(!vis[i]){
                bool ok=true;
                for(int j=1;j<=n;j++) if(j!=p[i]) ok&=used[j]||e[i][j]<=e[i][p[i]];
                if(ok){vis[i]=used[p[i]]=true;Q.push_back(i);flag=true;}
            }
            if(!flag) break;
        }
        for(auto &i:Q) i--;
        auto P=query(Q);
        for(auto &i:Q) i++;
        for(auto &i:P) i.first++;
        ll s=0;
        for(int i=0;i<n;i++){
            s+=P[Q[i]-1].second;
            for(int j=0;j<=i;j++) chkmin(e[Q[j]][P[Q[i]-1].first],P[Q[j]-1].second-(i!=j));
        }
        if(s==E){
            for(auto &i:Q) i--;
            return Q;
        }
    }
}