L. Yet another roads problem
Example
input
7
42 21 5 6 7 3 9
output
41
題目大意
給定N個城市，以及每個城市的居民人數，要求修最少條數的道路使這N座城市連通，并要求最大化經濟增長，求總經濟增長的最大值，在兩座城市之間修路的前提下，經濟增長等于兩個城市居民人數的最大公約數，
分析
首先可以確定最少道路條數是N-1，接下來的問題就類似于最小生成樹，在兩個城市之間連邊，優先選擇最大公約數大的兩個城市之間相連，還要用并查集檢查兩個城市之間是否已經連邊，
具體做法是將每個數字的編號放到它的所有約數的集合里，再從大到小列舉公約數，如果兩個城市之間沒有連邊，就相連，并記錄經濟增長，最終就可以求得總經濟增長的最大值，
AC代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
vector<int> v[N];
int p[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) p[i]=i;
int mx=0;
ll ans=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
mx=max(mx,x);
for(int j=1;j*j<=x;j++)
{
if(x%j==0)
{
v[j].push_back(i);
if(j*j!=x) v[x/j].push_back(i);
}
}
}
for(int i=mx;i>0;i--)
{
for(int j=1;j<v[i].size();j++)
{
int x=find(v[i][j-1]);
int y=find(v[i][j]);
if(x!=y)
{
ans+=i;
p[x]=y;
}
}
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/264514.html
標籤：其他
上一篇：qt與duilib對比