1 #include<cstdio> 2 const int inf=0x3f3f3f3f; 3 class Prim{///最小生成树(无向图)o(MV^2)要保证图连通 4     typedef int typec;///边权的类型 5     static const int MV=32;///点的个数 6     int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1 7     bool vis[MV]; 8     typec mat[MV][MV],dist[MV],res; 9 public:10     void init(int tn){///传入点数，点下标0开始11         n=tn;12         for(i=0;i<n;i++)13             for(j=0;j<n;j++)14                 mat[i][j]=i==j?0:inf;///不相邻点边权inf15     }16     void add(int u,int v,typec w){17         if(mat[u][v]>w){18             mat[u][v]=w;19             mat[v][u]=w;20         }21     }22     int solve(){///返回最小生成树的长度23         for(res=i=0;i<n;i++){24             dist[i]=inf;25             vis[i]=false;26             pre[i]=-1;27         }28         for(dist[j=0]=0;j<n;j++){29             for(k=-1,i=0;i<n;i++){30                 if(!vis[i]&&(k==-1||dist[i]<dist[k])){31                     k=i;32                 }33             }34             for(vis[k]=true,res+=dist[k],i=0;i<n;i++){35                 if(!vis[i]&&mat[k][i]<dist[i]){36                     dist[i]=mat[pre[i]=k][i];37                 }38             }39         }40         return res;41     }42 }gx;43 int main() {44     int n;45     char op[4];46     while(~scanf("%d",&n),n){47         gx.init(n);48         for(int i=0,num,val;i<n-1;i++){49             scanf("%s%d",op,&num);50             while(num--){51                 scanf("%s%d",op,&val);52                 gx.add(i,op[0]-‘A‘,val);53                 gx.add(op[0]-‘A‘,i,val);54             }55         }56         printf("%d\n",gx.solve());57     }58     return 0;59 }

 1 #include<cstdio> 2 const int inf=0x3f3f3f3f; 3 class Prim { ///最小生成树(无向图)o(MV^2)要保证图连通 4     typedef int typec;///边权的类型 5     static const int MV=128;///点的个数 6     int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1 7     bool vis[MV]; 8     typec mat[MV][MV],dist[MV],res; 9 public:10     void init(int tn) { ///传入点数，点下标0开始11         n=tn;12         for(i=0; i<n; i++)13             for(j=0; j<n; j++)14                 mat[i][j]=i==j?0:inf;///不相邻点边权inf15     }16     void add(int u,int v,typec w) {17         if(mat[u][v]>w) {18             mat[u][v]=w;19             mat[v][u]=w;20         }21     }22     int solve() { ///返回最小生成树的长度23         for(res=i=0; i<n; i++) {24             dist[i]=inf;25             vis[i]=false;26             pre[i]=-1;27         }28         for(dist[j=0]=0; j<n; j++) {29             for(k=-1,i=0; i<n; i++) {30                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {31                     k=i;32                 }33             }34             for(vis[k]=true,res+=dist[k],i=0; i<n; i++) {35                 if(!vis[i]&&mat[k][i]<dist[i]) {36                     dist[i]=mat[pre[i]=k][i];37                 }38             }39         }40         return res;41     }42 }gx;43 int main(){44     int n;45     while(~scanf("%d",&n)){46         gx.init(n);47         for(int i=0,w;i<n;i++){48             for(int j=0;j<n;j++){49                 scanf("%d",&w);50                 gx.add(i,j,w);51             }52         }53         printf("%d\n",gx.solve());54     }55     return 0;56 }

 1 #include<cstdio> 2 const int inf=0x3f3f3f3f; 3 class Prim { ///最小生成树(无向图)o(MV^2)要保证图连通 4     typedef int typec;///边权的类型 5     static const int MV=2048;///点的个数 6     int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1 7     bool vis[MV]; 8     typec mat[MV][MV],dist[MV],res; 9 public:10     void init(int tn) { ///传入点数，点下标0开始11         n=tn;12         for(i=0; i<n; i++)13             for(j=0; j<n; j++)14                 mat[i][j]=i==j?0:inf;///不相邻点边权inf15     }16     void add(int u,int v,typec w) {17         if(mat[u][v]>w) {18             mat[u][v]=w;19             mat[v][u]=w;20         }21     }22     int solve() { ///返回最小生成树的长度23         for(res=i=0; i<n; i++) {24             dist[i]=inf;25             vis[i]=false;26             pre[i]=-1;27         }28         for(dist[j=0]=0; j<n; j++) {29             for(k=-1,i=0; i<n; i++) {30                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {31                     k=i;32                 }33             }34             for(vis[k]=true,res+=dist[k],i=0; i<n; i++) {35                 if(!vis[i]&&mat[k][i]<dist[i]) {36                     dist[i]=mat[pre[i]=k][i];37                 }38             }39         }40         return res;41     }42 }gx;43 struct S{44     char s[8];45 }str[2048];46 int main(){47     int n;48     while(~scanf("%d",&n),n){49         gx.init(n);50          for(int i=0;i<n;i++){51             scanf("%s",str[i].s);52         }53         for(int i=0;i<n;i++){54             for(int j=i+1;j<n;j++){55                 int val=0;56                 for(int k=0;k<7;k++){57                     if(str[i].s[k]!=str[j].s[k]){58                         val++;59                     }60                 }61                 gx.add(i,j,val);62             }63         }64         printf("The highest possible quality is 1/%d.\n",gx.solve());65     }66     return 0;67 }

 1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 const int inf=0x3f3f3f3f; 6 class Prim { ///最小生成树(无向图)o(MV^2)要保证图连通 7     typedef double typec;///边权的类型 8     static const int MV=512;///点的个数 9     int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-110     bool vis[MV];11 public:12     typec mat[MV][MV],dist[MV],res;13 public:14     void init(int tn) { ///传入点数，点下标0开始15         n=tn;16         for(i=0; i<n; i++)17             for(j=0; j<n; j++)18                 mat[i][j]=i==j?0:inf;///不相邻点边权inf19     }20     void add(int u,int v,typec w) {21         if(mat[u][v]>w) {22             mat[u][v]=w;23             mat[v][u]=w;24         }25     }26     typec solve() { ///返回最小生成树的长度27         for(res=i=0; i<n; i++) {28             dist[i]=inf;29             vis[i]=false;30             pre[i]=-1;31         }32         for(dist[j=0]=0; j<n; j++) {33             for(k=-1,i=0; i<n; i++) {34                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {35                     k=i;36                 }37             }38             for(vis[k]=true,res+=dist[k],i=0; i<n; i++) {39                 if(!vis[i]&&mat[k][i]<dist[i]) {40                     dist[i]=mat[pre[i]=k][i];41                 }42             }43         }44         return res;45     }46 }gx;47 struct P{48     double x,y;49 }p[512];50 int main(){51     int t,n,m;52     while(~scanf("%d",&t)){53         while(t--){54             scanf("%d%d",&n,&m);55             for(int i=0;i<m;i++){56                 scanf("%lf%lf",&p[i].x,&p[i].y);57             }58             gx.init(m);59             for(int i=0;i<m;i++){60                 for(int j=0;j<m;j++){61                     gx.add(i,j,sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)));62                 }63             }64             gx.solve();65             sort(gx.dist,gx.dist+m);66             printf("%.2f\n",gx.dist[m-n]);67         }68     }69     return 0;70 }

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int inf=0x3f3f3f3f; 5 class Prim { ///最小生成树(无向图)o(MV^2)要保证图连通 6     typedef int typec;///边权的类型 7     static const int MV=512;///点的个数 8     int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1 9     bool vis[MV];10 public:11     typec mat[MV][MV],dist[MV],res;12 public:13     void init(int tn) { ///传入点数，点下标0开始14         n=tn;15         for(i=0; i<n; i++)16             for(j=0; j<n; j++)17                 mat[i][j]=i==j?0:inf;///不相邻点边权inf18     }19     void add(int u,int v,typec w) {20         if(mat[u][v]>w) {21             mat[u][v]=w;22             mat[v][u]=w;23         }24     }25     typec solve() { ///返回最小生成树的长度26         for(res=i=0; i<n; i++) {27             dist[i]=inf;28             vis[i]=false;29             pre[i]=-1;30         }31         for(dist[j=0]=0; j<n; j++) {32             for(k=-1,i=0; i<n; i++) {33                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {34                     k=i;35                 }36             }37             for(vis[k]=true,res+=dist[k],i=0; i<n; i++) {38                 if(!vis[i]&&mat[k][i]<dist[i]) {39                     dist[i]=mat[pre[i]=k][i];40                 }41             }42         }43         return res;44     }45 }gx;46 int main(){47     int t,n;48     while(~scanf("%d",&t)){49         while(t--){50             scanf("%d",&n);51             gx.init(n);52             for(int i=0,w;i<n;i++){53                 for(int j=0;j<n;j++){54                     scanf("%d",&w);55                     gx.add(i,j,w);56                 }57             }58             gx.solve();59             int ans=0;60             for(int i=1;i<n;i++){61                 ans=max(ans,gx.dist[i]);62             }63             printf("%d\n",ans);64         }65     }66     return 0;67 }