自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 23:11:05，当前版本为作者最后更新于2025-06-08 01:17:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑如果我们知道了所有的 $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;
		}
	}
}