题意：给N个城市，用电缆将所有城市连接起来。
思路：最小生成树模板题,kruskal算法的应用。
代码：
#include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 600 #define INF 1<<25 #define MAX 0x7fffffff typedef long long ll; using namespace std; string c[maxn]; int vv[maxn]; struct Road { int v,w; double l; } road[maxn*maxn]; bool cmp(Road a,Road b) { return a.l xx) { vv[yy]=xx; } else vv[xx]=yy; return 1; } int main() { double len,k,ans=0,tt=0; string x,y; int cc,rr,a,b; memset(vv,0,sizeof(vv)); scanf(%lf,&len); scanf(%d,&cc); for(int i=1; i<=cc; i++) { vv[i]=i; cin>>c[i]; } scanf(%d,&rr); for(int ii=0; ii >x>>y>>k; for(int i=1; i<=cc; i++) { if(c[i]==x) a=i; if(c[i]==y) b=i; } road[ii].v=a; road[ii].w=b; road[ii].l=k; } sort(road,road+rr,cmp); for(int i=0; i