题解归档 - cf104114F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114F
• 本地来源：problems/cf104114F/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/F
• 原始标题：cf104114F - Fortune over Sportsmanship

思路

cf104114F - Fortune over Sportsmanship

After several matches, the only alive player in a merged group is the smallest-index player of that group. Because winners inherit row/column maxima, the current popularity between two alive representatives equals the maximum original P[u][v] over the two groups.

So choosing a match between two current groups is exactly choosing an edge between two DSU components with weight equal to the maximum crossing edge. To maximize the sum over n-1 merges, run Kruskal for a maximum spanning tree on the complete graph weighted by P.

Process edges in descending weight. When an edge connects two components, output the current alive representatives of those components and merge them. The lower-numbered representative will be the winner by the statement rules.

Complexity: O(n^2 log n) for n <= 1000.

代码

来源：problems/cf104114F/solution.cpp

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct Edge{
    int u,v,w;
    bool operator<(const Edge&o)const{
        return w>o.w;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    vector<Edge> e;
    e.reserve(1LL*n*(n-1)/2);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int w;
            cin>>w;
            if(i<j) e.push_back({i,j,w});
        }
    }
    sort(e.begin(),e.end());

    vector<int> fa(n+1),rep(n+1);
    iota(fa.begin(),fa.end(),0);
    iota(rep.begin(),rep.end(),0);
    auto find=[&](auto self,int x)->int{
        return fa[x]==x?x:fa[x]=self(self,fa[x]);
    };

    ll ans=0;
    vector<pair<int,int>> out;
    for(auto [u,v,w]:e){
        int ru=find(find,u),rv=find(find,v);
        if(ru==rv) continue;
        int a=rep[ru],b=rep[rv];
        out.push_back({a,b});
        ans+=w;
        if(rep[ru]>rep[rv]) swap(ru,rv);
        fa[rv]=ru;
        rep[ru]=min(rep[ru],rep[rv]);
        if((int)out.size()==n-1) break;
    }

    cout<<ans<<"\n";
    for(auto [a,b]:out) cout<<a<<" "<<b<<"\n";
    return 0;
}