CF1095F Make It Connected

2022-09-22 20:02:45 字數 1059 閱讀 7994

cf1095f make it connected

一眼kruskal板子題,又看了一眼被資料範圍勸退,去原題看了一眼div3的題,仔細思考了一下。

我們把所有邊考慮一下,除了特殊邊,剩下邊都是 \(a_i + a_j\) 的形式。那麼顯然,在固定一個的情況下,一個最小肯定最優,那麼我們容易想到一定存在一個 \(a_\) 使得 \(a_ + a_ \le a_ + a_\) 那麼我們只需要 \(a_+a_\) 的 \(n-1\) 條邊和 \(m\) 條特殊邊就行了。

#include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10, inf = 0x3f3f3f3f3f3f3f3f;

ll n, m, fa[maxn], val[maxn];

struct edge

edge() {}

friend bool operator < (edge a, edge b)

} e[maxn];

ll ans = 0, minn = inf, mini = 0;

ll find_(ll);

void onion(ll, ll);

int main()

for (ll i = 1; i <= m; i++)

for (ll i = 1; i <= n; i++) if (i != mini)

e[++m] = edge(i, mini, val[i] + val[mini]);

sort(e+1, e+m+1);

for (ll i = 1, qq = 1; i < n && qq <= m; i++, qq++)

onion(fx, fy);

ans += e[qq].v;

}printf("%lld\n", ans);

return 0;

}void onion(ll x, ll y)

}ll find_(ll x)