ural 1416 Confidential

ural 1416 Confidential

​​ Zaphod Beeblebrox — President of the Imperial Galactic Government. And by chance he is an owner of enterprises that trade in secondhand pens. This is a complicated highly protable and highly competitive business. If you want to stay a leader you are to minimize your expenses all the time. And the presedent’s high post helps in those aairs. But he is to keep this business in secret. As a president Zaphod has access to the top secret and important information an exact value of power loss in the hyperspace transition between the planets. Of course, this information is very useful to his company. Zaphod is to choose the minimal possible set of trans-planet passages so that he could pass from any planet to any other one via those passages and their total cost would be minimal. The task won’t be complicated if Zaphod was not to keep in secret that he helps his company with the secret information. Thus, Zaphod decided to find not the cheapest passages set but the next one. As a real businessman he wants to estimate the value of his conspiracy expenses. Input The first line contains integers n and m that are a number of planets in the Galaxy and an amount of passages between them (2 ≤ n ≤ 500). The next m lines contain integers ai, bi and wi that are the numbers of the planets connected with the passage and the transition cost (1 ≤ ai, bi ≤ n; 0 ≤ wi ≤ 1000). If an A to B transition is possible then a B to A transition is possible too, and the cost of these transitions are equal. There is no more than one passage between any two planets. One can reach any planet from any other planet via some chain of these passages. Output You should find two different sets of transitions with the minimal possible cost and output theirs costs. Print the minimal possible cost first. If any of those sets of transitions does not exist denote it’s cost by −1. Samples input output 4 6 1 2 2 2 3 2 3 4 2 4 1 2 1 3 1 2 4 1 Cost: 4 Cost: 4 3 2 1 2 2 2 3 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("ural1416.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小时内删除侵权内容。