vijos1070 新年趣事

vijos1070 新年趣事

​​ 描述

xiaomengxian的哥哥是一个游戏迷，他喜欢研究各种游戏。这天，xiaomengxian到他家玩，他便拿出了自己最近正在研究的一个游戏给xiaomengxian看。这个游戏是这样的：一个国家有N个城市，有些城市之间可以建设铁路，并且不同城市之间建设铁路的费用各不相同。问如何用最小的费用，使整个国家的各个城市之间能够互相到达。另外，铁路是双向的。xiaomengxian心想，这不是太简单了吗？这就是经典的MST问题。他的哥哥说，这个当然不算什么。关键是它还要求费用第二小的方案，这真是让人伤脑筋。xiaomengxian想了很久，也没有想出来，你能帮助他吗？ 费用第二小的方案的定义为：与费用最小的方案不完全相同，且费用值除费用最小的方案外最小。

格式

输入格式

第一行两个数N（2<=N<=500），M，分别表示国家的城市数和可以修建铁路的城市有多少对。

接下来M行，每行三个正整数Ai，Bi，Ci，表示城市Ai和Bi之间可以修建铁路，费用为Ci。

输出格式

第一行：”Cost: “+一个整数，表示最小费用。（若不存在，输出-1） 第二行：”Cost: “+一个整数，表示第二小费用。（若不存在，输出-1）

样例1

样例输入1

4 6 1 2 2 2 3 2 3 4 2 4 1 2 1 3 1 2 4 1 Copy 样例输出1

Cost: 4 Cost: 4 Copy 限制

各个测试点1s

提示

Sample input #2 3 2 1 2 2 2 3 2

Sample output #2 Cost: 4 Cost: -1

次小生成树 ：思路就是我们先建立一棵最小生成树

然后枚举非树边 然后把两个端点树上路径的最大值找出来，求出最大值和非树边权值差 找到权值差最小即可

#include#include#include#define N 550using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1;ch=getchar(); } while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int x,y,z,next;}data[N*N],data1[N<<1];int fa1[N],m,n,h[N],fa[N][20],st[N][20],dep[N],qq,Log[N];bool visit[N*N];inline bool cmp(node a,node b){return a.z=0;--j){ if (fa[x][j]!=fa[y][j]){ min1=max(min1,st[x][j]);min1=max(min1,st[y][j]);x=fa[x][j];y=fa[y][j]; } } return max(min1,max(st[x][0],st[y][0]));}int main(){ freopen("vijos1070.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); data[i].x=x;data[i].y=y;data[i].z=z; } sort(data+1,data+m+1,cmp); for (int i=1;i<=n;++i) fa1[i]=i;int cnt=0,num=0,ans=0; for (int i=1;i<=m;++i){ int x=data[i].x,y=data[i].y,z=data[i].z; int xx=find(x),yy=find(y); if (xx!=yy){ ++cnt;data1[++num].y=y;data1[num].z=data[i].z;data1[num].next=h[x];h[x]=num;data1[num].x=x; data1[++num].y=x;data1[num].z=data[i].z;data1[num].next=h[y];h[y]=num;fa1[xx]=yy;data1[num].x=y; visit[i]=true;ans+=z; if (cnt==n-1) break; } } //for (int i=1;i<=num;++i) printf("%d %d %d\n",data1[i].x,data1[i].y,data1[i].z);printf("asdfasd\n");// if (cnt>1]+1; dep[1]=1;dfs1(1);bool flag=false;int ans1=0x7f7f7f7f; for (int i=1;i<=m;++i){ if (!visit[i]){ int x=data[i].x,y=data[i].y,z=data[i].z; int max1=lca(x,y); if (z-max1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。