难点：找到正确方式建图

知识点：Kruskal

 

分析：这种题肯定要把点权转换到边权上，但肯定无法搞到和其他点相连的边上，怎么办呢？那就再造一个点呗，这个“超级点”和所有点相连，且边权=点权，于是就可以消除点权对选择的影响，代码实现很简单，思路不好想

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;  6 inline int read(){  7     char chr=getchar();    int f=1,ans=0;  8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}  9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} 10     return ans*f; 11 } 12 void write(int x){ 13     if(x<0) putchar('-'),x=-x; 14     if(x>9) write(x/10); 15     putchar(x%10+'0'); 16 }int n,w[1005],fa[1005],tot,ans; 17 struct P{int x,y,z;}a[900005],t; 18 bool operator < (const P &x,const P &y){return x.z<y.z;} 19 int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);} 20 void Kruskal(){ 21     for(int i=0;i<=n;i++) fa[i]=i; 22     sort(a+1,a+tot+1);int e=0; 23     for(int i=i;i<=tot;i++){ 24         int fx=find(a[i].x),fy=find(a[i].y); 25         if(fx==fy) continue;++e; 26         fa[fx]=fy;ans+=a[i].z; 27         if(e==n) break;//多了一个点，所以不用e==n-1 28  }write(ans); 29 }int main(){ 30     n=read(); 31     for(int i=1;i<=n;i++) w[i]=read(); 32     for(int i=1;i<=n;i++)a[++tot]=P{0,i,w[i]};//超级源点0 33     for(int i=1;i<=n;i++) 34         for(int j=1;j<=n;j++) 35             (i==j)?t={i,j,read()}:a[++tot]={i,j,read()}; 36  Kruskal(); 37     return 0; 38 }