luogu 1550 [Usaco2008 Oct]打井 最小生成树+小技巧

时间：2024-01-16 09:51:14

此题似乎显然最小生成树，小技巧需要注意：

在每个点出井水，需要花费，实际上可以把井水视作所有井下统一的一点，需要走路径到达此点，新图上再最小生成树

将点化作边处理

还有题目写的数据范围一般不可信，开大点总是好的，代码就不贴了吧

#include<bits/stdc++.h>

#define rep(i,x,y) for(register ll i=x;i<=y;i++)

#define ll long long

using namespace std;

const ll N=;

const ll M=;

inline ll read(){

    ll x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;}

ll n,m,a[N],g[N][N],x,cnt,xx,yy,fa[N];ll ans;

inline ll find(ll x){return fa[x]==x?x:fa[x]=find(fa[x]);}

struct node{ll u,v,w;}e[M];

bool cmp(node a,node b){return a.w<b.w;}

int main(){

    n=read();cnt=n+;

    rep(i,,n) fa[i]=i,x=read(),e[++m]=(node){i,n+,x};fa[n+]=n+;

    rep(i,,n)rep(j,,n) g[i][j]=read();

    rep(i,,n)rep(j,i+,n) e[++m]=(node){i,j,g[i][j]};

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

    rep(i,,m){

        xx=find(e[i].u),yy=find(e[i].v);

        if(xx!=yy) fa[xx]=yy,cnt--,ans+=e[i].w;

        if(cnt==) break;

    }printf("%d\n",ans);return ;

}

相关文章