做网站先用dw还是asp,网站开发需要哪些知识和工具,百度推广没有一点效果,温州论坛招聘第一题#xff1a;longest 乌托邦有n个城市#xff0c;某些城市之间有公路连接。任意两个城市都可以通过公路直接或者间接到达#xff0c;并且任意两个城市之间有且仅有一条路径#xff08;What does this imply? A tree!#xff09;。 每条公路都有自己的长度#xff0…第一题longest 乌托邦有n个城市某些城市之间有公路连接。任意两个城市都可以通过公路直接或者间接到达并且任意两个城市之间有且仅有一条路径What does this imply? A tree!。 每条公路都有自己的长度这些长度都是已经测量好的。 小修想从一个城市出发开车到另一个城市并且她希望经过的公路总长度最长。请问她应该选择哪两个城市这个最长的长度是多少 Input format 第一行nn1000。 以下n-1行每行三个整数a, b, c。表示城市a和城市b之间有公路直接连接并且公路的长度是c(c10000)。 Output format 仅一个数即最长长度。 Sample Longest.in 5 1 2 2 2 3 1 2 4 3 1 5 4 Longest.out 9 说明从城市4到城市5经过的路径是4-2-1-5总长度是9。 裸的kruskal吧 没什么好说的模板题 上代码o(〃▽〃)o #includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,m;
struct node{int u;int v;int value;
}e[1001];
int father[1001];
bool cmp(node e1,node e2)
{return e1.valuee2.value;
}
void read()
{scanf(%d,n);m0;for(int i1;in;i){m;int u,v,w;scanf(%d%d%d,u,v,w);e[m].uu;e[m].vv;e[m].valuew;}sort(e1,em1,cmp);
}
int find(int x)
{if(father[x]x) return x;else return father[x]find(father[x]);
}
void merge(int x,int y)
{if(father[x]!father[y]) father[father[x]]father[y];
}
void kruskal()
{int sum0;int ans0;for(int i1;in;i) father[i]i;for(int i1;im;i){if(find(e[i].u)!find(e[i].v)){sum;anse[i].value;merge(e[i].u,e[i].v);}if(sumn-2){printf(%d,ans);return ;}}printf(%d,-1);
}
int main()
{read();kruskal();return 0;
} View Code 转载于:https://www.cnblogs.com/orange-/p/4887850.html
