#include <bits/stdc++.h>
using namespace std;
struct ufds {
int n;
vector<int> par;
ufds(int _n): n(_n), par(_n,-1) {}
int onion(int x) {return (par[x]<0?x:par[x]=onion(par[x]));}
bool unite(int x, int y) {
x=onion(x), y=onion(y);
if(x==y)
return 0;
if(par[x]<par[y])
swap(x,y);
par[y]+=par[x];
par[x]=y;
return 1;
}
};
long long mst(int n, vector<tuple<int,int,int>> edge) {
sort(edge.begin(),edge.end());
long long ans = 0;
ufds dsu(n);
for(auto [w, u, v]: edge)
if(dsu.unite(u,v))
ans += w;
return ans;
}
int main() {
int n, m, q;
cin >> n >> m >> q;
int s[n], d[n];
for(int i=0;i<n;i++)
cin >> s[i];
memset(d,0,sizeof(d));
vector<tuple<int,int,int>> edge;
for(int i=0;i<m;i++) {
int a, b;
cin >> a >> b;
a--; b--;
edge.push_back({s[a]+s[b],a,b});
}
int small = min_element(s,s+n)-s;
long long ans[n];
memset(ans,1,sizeof(ans));
for(int i=0;i<(1<<n);i++) {
for(int j=0;j<n;j++)
if(i&(1<<j))
edge.push_back({s[small]+s[j],small,j});
ans[__builtin_popcount(i)] = min(ans[__builtin_popcount(i)], mst(n,edge));
edge.resize(m);
}
long long delta = 0;
for(int i=0;i<n;i++)
delta -= s[i];
delta += *max_element(s,s+n);
for(int i=0;i<=q;i++)
cout << ans[min(i,n-1)] + delta << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |