Build

uuku · 2022-07-13 22:55:25 · 题解

不难发现，每个小镇花费的价钱只与该小镇建了多少条公路有关，与和哪个小镇建的无关。而每个小镇修建的条数就是最后生成的途中该点的度数，记为 du_i。

所以我们不妨从每个小镇的角度进行求解。将每个小镇修建下一条公路的代价排序后取最小值。显然修建 m 条道路，即 \sum\limits_{i=1}^n du_i=2m。所以只需取 2m 次最小值即可。

上述过程可以用堆维护。

但是还没结束，还要满足图连通和没有自环两个条件。

图连通的一个显然的必要条件是 \forall i \in [1,n],du_i>0。

无自环的一个显然的必要条件是 \forall i \in [1,n],du_i\le m。

下面给出构造方案以证明充分性：

我们只需不断的将当前度数最小值的点连向度数最大值的点即可。

证明连通性

考虑当当前的度数最小值是 1 时，连了这条边之后它将无法再和其它点连边。但是连了这条边之后，它将和当前的度数最大的点连通。

而之前和它连通的点（可能没有），也会间接的和剩下的点连通。

也就是说每个度数变为 0 的点都会直接或间接的和当前剩下的度数不为 0 的点连通。

所以最终这 n 个点会连通。

证明无自环

考虑用反证法，假设最终会产生自环，即 \exists i \in [1,n],du_i>0。而由于总度数是偶数，每次连边也会使总度数减 2。所以 du_i\ge 2 且 du_i \bmod 2=0。

示例代码：

#define pli pair<ll,int>
const int N = 2e5 + 10;
int n, m, du;
ll ans;
struct P{
    int id, a, b, c, cnt;
    inline void rd(int i){id = i, cin >> a >> b >> c;}
    inline ll get(){cnt++; return (1ll * a * cnt + b) * cnt + c;}
} v[N];
priority_queue<pli, vector<pli>, greater<pli>> q;
pli now;
inline bool cmp(P x, P y){return x.cnt > y.cnt;}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m, du = m << 1;
    for(int i = 1; i <= n; ++i) v[i].rd(i);

    for(int i = 1; i <= n; ++i) ans += v[i].get();
    du -= n;

    for(int i = 1; i <= n; ++i) q.push(make_pair(v[i].get(), i));

    while(du--)
    {
        now = q.top(), q.pop();
        ans += now.first;
        if(v[now.second].cnt == m){v[now.second].cnt++;continue;}
        q.push(make_pair(v[now.second].get(), now.second));     
    }
    for(int i = 1; i <= n; i++) v[i].cnt--; 

    cout<<ans<<'\n';

    sort(v + 1, v + n  + 1, cmp);
    int l = 1, r = n;
    while(v[r].cnt == 0) r--;
    while(l < r)
    {
        if(v[1].cnt == 1)break;
        cout<<v[r].id<<' '<<v[l].id<<'\n';
        v[r].cnt--, v[l].cnt--;
        l++;
        if(v[l].cnt <= v[1].cnt && v[1].cnt) l = 1;
        if(!v[r].cnt) r--;
        if(l == r && v[l].cnt)swap(v[l], v[1]), l = 1;
    }
    if(v[1].cnt)
    {
        for(int i = 2; i <= n; i++)
            if(v[i].cnt)
            {
                cout<<v[i].id<<' '<<v[i-1].id<<"\n";
                v[i].cnt--, v[i-1].cnt--;
            }
    }
    return 0;
}

赛时选手提供的爆标思路

同样只考虑每个点的度数，显然会有一个最大值，我们不妨直接二分这个最大值。然后可以用二次函数求根公式快速计算每个点选了多少次。然后判断总度数是否达到 2m 且每个点度数仍符合上述条件即可。复杂度可以做到 O(n\log V+m)。