CF补题大作战#4

碎碎念

放个假在家颓废了两天

结果看到连续两周都有很厉害的学长学姐打铁

压力感和紧迫感一下子就出现了

就剩20天了，还有什么时间给我浪费啊呜呜呜

CF1728F Fishermen

给你一个数组a，求和最小的数组b使得

b中元素各不相同，且b[i]是a[i]的倍数

n<=1000，a[i]<=10^6

solution

显然可以建出一个二分图模型，左边是a[i]

对于每个a[i]，可以对a[i]*(1~n)连一条边，所以右边的点的数量为10^6

每条边的代价即为右边的点值，但是二分图最小权匹配显然过不了
网络流也不太可能跑过10^6个点10^6条边的图

考虑普通二分图匹配，我们只要贪心的从右边最小的点开始匹配即可

这个贪心性质如果细想的话没那么显然，但是不太想证明了qwq

这样做的话，复杂度是n^4，考虑优化匹配的过程

如果一次匹配失败，那么vis数组不用清空，因为下一次匹配这个点一定失败

这样复杂度就优化到n^3，又因为时限是6s，咋写都能过了

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
int n,m,cnt,a[1010],b[1000010],vis[1010],match[1010];
map<int,int>mp;
vector<int>e[1000010];
int dfs(int u)
{
	for(auto v:e[u])
	{
		if(vis[v])continue;
		vis[v]=1;
		if(!match[v]||dfs(match[v]))
		{
			match[v]=u;
			return 1;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		for(int j=1;j<=n;j++)
			b[++m]=a[i]*j;
	}
	sort(b+1,b+m+1);
	for(int i=1;i<=m;i++)
		if(b[i]!=b[i-1])
			mp[b[i]]=++cnt;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			e[mp[a[i]*j]].pb(i);
	ll ans=0;
	for(auto i:mp)
		if(dfs(i.second))
			ans+=i.first,memset(vis,0,sizeof(vis));
	cout << ans << endl;
	return 0;
}