考察:最小生成树
思路:
一眼扫过去超像Prim算法,实际上最小生成树的两种方法皆可.当我们刚开始建矿井时就像有个虚拟源点向实点伸展了一条边,所以建立个虚拟原点即可.
这道题是无向边所以不用管u,v到底哪个是被建矿井的端点.
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N = 310; 6 int n,cnt,x,p[N],res; 7 struct Road{ 8 int u,v,w; 9 bool operator<(const Road& r)const{ 10 return this->w<r.w; 11 } 12 }road[N*N]; 13 int findf(int x) 14 { 15 if(x!=p[x]) p[x] = findf(p[x]); 16 return p[x]; 17 } 18 int main() 19 { 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++) p[i] = i; 22 for(int i=1;i<=n;i++) 23 { 24 scanf("%d",&x); 25 road[++cnt].w = x; 26 road[cnt].u = 0,road[cnt].v = i; 27 } 28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=n;j++) 30 { 31 scanf("%d",&x); 32 if(i<=j) continue; 33 road[++cnt].w = x; 34 road[cnt].u = i,road[cnt].v = j; 35 } 36 sort(road+1,road+cnt+1); 37 for(int i=1;i<=cnt;i++) 38 { 39 int pa = findf(road[i].u),pb = findf(road[i].v); 40 if(pa==pb) continue; 41 res += road[i].w; 42 p[pa] = pb; 43 } 44 printf("%d\n",res); 45 return 0; 46 }