wordpress主题开发网站,网站建设公司新,柳州做网站的企业,业务外包服务公司题目
有n个村#xff0c;m条路#xff0c;给n-1条路刷油漆连接n个村#xff0c;让最长边与最短边的长度差最小。 输入输出#xff08;建议跳过#xff09;
Input
第一行给出一个数字TOT#xff0c;代表有多少组数据,Tot6 对于每组数据#xff0c;首先给出N…题目
有n个村m条路给n-1条路刷油漆连接n个村让最长边与最短边的长度差最小。 输入输出建议跳过
Input
第一行给出一个数字TOT代表有多少组数据,Tot6 对于每组数据首先给出NM 下面M行每行三个数a,b,c代表a村与b的村道路距离为c.
Output
输出最小差值,如果无解输出”-1”.
Sample Input
1 4 5 1 2 3 1 3 5 1 4 6 2 4 6 3 4 7
Sample Output
1 解题思路
这道题数据比较小首先记录下所有边然后排序。枚举最大边然后用并查集确定“村村通”的关系然后取最小值。 代码
#includecstdio
#includealgorithm
#includeiostream
using namespace std;
struct line{int x,y,w;
}a[4951];//记录边
int father[101],n,mins,t,m;
bool cmp(line dx,line dy)
{return dx.wdy.w;
}//快排用
int find(int x)
{if (x!father[x]) return father[x]find(father[x]);return x;
}//并查集
void d(int x,int y)
{father[find(x)]find(y);
}//连接
int main()
{scanf(%d,t);for (int ti1;tit;ti){scanf(%d%d,n,m);for (int i1;im;i){scanf(%d%d%d,a[i].x,a[i].y,a[i].w);}sort(a1,a1m,cmp);//快排mins214748364;for (int i1;im;i)//枚举最小边{int ji1,k1;//j表示枚举到的边k表示选择了的边for (int q1;qn;q) father[q]q;d(a[i].x,a[i].y);while (jm){if (find(a[j].x)!find(a[j].y))//如果没连接{d(a[j].x,a[j].y);//连接k;//记录}j1;//下一条if (kn-1) break;//边数足够}if (j-1m kn-1)minsmin(mins,a[i].w-a[j-1].w);//取最小}if (n2 m1 a[1].x!a[1].y) printf(0);//特殊情况判断else if (mins214748364) printf(-1\n);//无法连接else printf(%d\n,mins);//输出}
}
