P5687 [CSP-S2019 江西] 网格图

__S08577__ · 2025-10-16 08:27:11 · 题解

好题。

从kruscal的本质出发，我们是贪心连权值最小的边，如果出现环那么这条边就不连。

这道题也是类似，贪心考虑，不出现环的情况下，肯定是把一行或者一列全部连起来，代价是 w*(n-1)

但是如果出现环怎么办，考虑什么时候会出现环，当我们连的行数和列数都大于等于2时，会出现环。因为我们贪心连边，所以删边肯定是删当前边而不是前面的边。

考虑会删几条边，肯定是连了这一列或一行多出现的环，以连了一列为例，那么多出的环肯定是 连的行数 减一。因为考虑我们连的第一条行与第一条列是不被删除的，所以我们只要再连就肯定会出现新环。

所以少的代价就是 (y-1) \times a[i].x。

行同理。

代码

struct node{
    int x;
    int id;
}a[N];
bool cmp(node a,node b){
    return a.x<b.x;
}
signed main(){

//   freopen("a.in","r",stdin);
//   freopen("a.out","w",stdout);
    fst
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i].x;
        a[i].id=1;
    }
    for(int i=n+1;i<=n+m;i++) {
        cin>>a[i].x;
        a[i].id=2;
    }
    sort(a+1,a+1+n+m,cmp);
    int x=0,y=0;
    int res=0;
    for(int i=1;i<=n+m;i++){
        if(a[i].id==1){
            res+=a[i].x*(m-1);
            if(x<n) x++;
            else x=n;
            if(x>=2&&y>=2) res-=(y-1)*a[i].x;
        }
        if(a[i].id==2){
            res+=a[i].x*(n-1);
            if(y<m) y++;
            else y=n;
            if(x>=2&&y>=2) res-=(x-1)*a[i].x;
        }
    }
    cout<<res<<endl;
    return 0;
}