timus1982. Electrification Plan---最小生成树
每WA一次都发现自己方法错了。。
真是太无知了 原来一直都不知道最小生成树是干嘛的 这题基本就一裸的最小生成树了 见识见识
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <map>#define inf 0x3f3f3f3fusing namespace std;int n,k,vis[110],pp[110],co[110][110],cost[110],p,tmp,ans,minc;int prim(){ int i,j,p; ans=0; vis[1]=1; for(i=2;i<=n;i++) cost[i]=co[1][i]; for(i=2;i<=n;i++) { minc=inf; for(j=1;j<=n;j++) { if(!vis[j]&&minc>cost[j]) { minc=cost[j]; p=j; } } vis[p]=1; ans+=minc; for(j=1;j<=n;j++) { if(!vis[j]&&cost[j]>co[p][j]) cost[j]=co[p][j]; } } return ans;}int main(){ int i,j; while(~scanf("%d%d",&n,&k)) { memset(vis,0,sizeof vis); memset(pp,0,sizeof pp); for(i=0;i<k;i++) { scanf("%d",&p); pp[p]=1; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&co[i][j]); } } for(i=1;i<=n;i++)//处理下已知的电力塔 for(j=1;j<=n;j++) { if(pp[i]&&pp[j]) { co[i][j]=0; } } printf("%d\n",prim()); } return 0;}