不用真的建图，真的建图两人之间的代价不好算。
等价转化为对给定的ai找出bi，使得bi=k*a[i]，且互不相同
k的上界为n，简易证明：
[
若a[i]互不相等，全部选a[i]*n会比a[i]*(n+1)更好；
若存在一对a[i]相等，可以使其中一个数取n-1
若再存在一对，取n-1..
必能在n步内对所有的a[i]赋值完。
]
点和边都是n²级别，对每个i，向a[i]*k连边，跑最大匹配就可以满足互不相同(匹配的定义)
那b要尽可能小怎么保证？以及sigma(bi)要尽可能小怎么保证？
对所有的a[i]*k从小到大排序，逐个尝试是否能匹配，可以的话把a[i]*k加入答案
这样贪心地保证了sigma(bi)尽可能小，且b一定尽可能地小(否则会先被匹配到)
最后一个问题，匈牙利算法是点数*边数，在这题是n4方级别，优化：
如果上一次没匹配成功，可以不用清空vis数组(理解：如果没有匹配成功，再换个点效果也一样，只有匹配成功了才是一个新图)
嗯加了这个玄学的优化可以变成n3。
细节：
直接用a[i]*k做一个点的话会爆int数组，要开map
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000*1000+5 ;
int d,match[maxn],vis[maxn],l[maxn],n,m;
struct lys{
int from,to,nex;
}e[maxn<<1];
int cnt=0;
map<int,int>head;
// head 和 e是同级的
void add(int from,int to){
cnt++;e[cnt].from=from;e[cnt].to=to;e[cnt].nex=head[from];head[from]=cnt;
}
int dfs(int x)
{
for(int i=head[x];i;i=e[i].nex)
{ int to=e[i].to;
if(vis[to]) continue;
vis[to]=1;
if(!match[to]||dfs(match[to]))
{
match[to]=x;
return 1;
}
}
return 0;
}
int main()
{
//freopen("lys.in","r",stdin);
int tot=0;
cin>>n;
for(int i=1;i<=n;i++){
int w;cin>>w;
for(int j=1;j<=n;j++){
int p=w*j;
tot++;
l[tot]=p;
add(p,i);// build directed edge
}
}
sort(l+1,l+tot+1);
int len=unique(l+1,l+tot+1)-(l+1);
long long ans=0;
bool find=0;
for(int i=1;i<=len;i++)
{ // cout<<i<<" "<<l[i]<<endl;
if(find) memset(vis,0,sizeof(vis));
find=dfs(l[i]);
if(find) ans+=(long long)(l[i]);
}
cout<<ans;
}
标签：Educational,Rated,匹配,int,Codeforces,bi,vis,cnt,match From： https://www.cnblogs.com/liyishui2003/p/17083715.html