二 LightOJ 1002 最小生成树

Description

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0to n-1 and each road has a cost. There are m roads. You are given the number of my city t where
I belong. Now from each city you have to find the minimum cost to go to my city. The cost is defined by the cost of the maximum road you have used to go to my city.

For example, in the above picture, if we want to go from 0 to 4, then we can choose

1)      0 - 1 - 4 which costs 8, as 8 (1 - 4) is the maximum road we used

2)      0 - 2 - 4 which costs 9, as 9 (0 - 2) is the maximum road we used

3)      0 - 3 - 4 which costs 7, as 7 (3 - 4) is the maximum road we used

So, our result is 7, as we can use 0 - 3 - 4.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line and two integers n (1 ≤ n ≤ 500) and m (0 ≤ m ≤ 16000). The next m lines, each will contain three integers u, v, w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 20000) indicating
that there is a road between uand v with cost w. Then there will be a single integer t (0 ≤ t < n). There can be multiple roads between two cities.

Output

For each case, print the case number first. Then for all the cities (from 0 to n-1) you have to print the cost. If there is no such path, print ‘Impossible‘.

Sample Input

2

5 6

0 1 5

0 1 4

2 1 3

3 0 7

3 4 6

3 1 8

1

5 4

0 1 5

0 1 4

2 1 3

3 4 7

1

Sample Output

Case 1:

4

0

3

7

7

Case 2:

4

0

3

Impossible

Impossible


FA

kruskal

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

int ans[10000];
int bin[10000];
struct node
{
    int x,y,v;
} p[20000];
int pos;
int cmp(node p1,node p2)
{
    return p1.v<p2.v;
}

int Find(int x)
{
  return bin[x]==x?x:bin[x]=Find(bin[x]);
}
int n,m,s[1000];
int Kruskal()                  //最小生成树
{
    for(int i=0; i<n; i++)
        bin[i]=i;

    int num=0;
    for(int i=0; i<m; i++)
    {
        int f1=Find(bin[p[i].x]);
        int f2=Find(bin[p[i].y]);
        if(f1!=f2)
        {
            bin[f2]=f1;
            //num++;
        }
        f1=Find(bin[pos]);
        for(int j=0; j<n; j++)
        {
            if(j==pos||ans[j])
                continue;
            f2=Find(bin[j]);
            if(f1==f2)
                ans[j]=p[i].v;
        }
        //if(num==n-1)
        //break;
    }
}
int main()
{
    int T;int icase=0;
        scanf("%d",&T);
        while(T--)
        {

        	memset(ans,0,sizeof(ans));

            scanf("%d%d",&n,&m);
            for(int i=0; i<m; i++)
            {
                scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);
            }

            cin>>pos;
            sort(p,p+m,cmp);

            Kruskal();
            printf("Case %d:\n",++icase);   //此题因为icase总是初始化为一而错了好久
            for(int i=0; i<n; i++)
            {
                if(i==pos)
                {
                    puts("0");
                    continue;
                }
                if(!ans[i])
                    puts("Impossible");
                else printf("%d\n",ans[i]);
            }
        }
}

prim

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f

using namespace std;

int Edge[501][501];
int low[501];
int next[502];
int n,sum,m;
int a[501];
int Prim(int u0)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		low[i]=Edge[u0][i];
		next[i]=u0;
	}
	next[u0]=-1;
	int max=0;
	for(i=0;i<n-1;i++)
	{
		int min=INF;
		int v=-1;
		for(j=0;j<n;j++)
		{
			if(next[j]!=-1&&low[j]<min)
			{
				min=low[j];
				v=j;
			}
		}

		if(min>max)
			max=min;      //本体的核心
		if(!a[v])             //
			a[v]=max;

		if(v!=-1)
		{
			//printf("%d %d %d\n",next[v],v,low[v]);
			//sum+=low[v];

			next[v]=-1;
			for(j=0;j<n;j++)
			{
				if(next[j]!=-1 &&Edge[v][j]<low[j])
				{
					low[j]=Edge[v][j];
					next[j]=v;
				}
			}
		}
	}
	//printf("%d\n",sum);
}
int main()
{
	int T;
	scanf("%d",&T);
	for(int kk=1;kk<=T;kk++)
	{
		sum=0;
		scanf("%d%d",&n,&m);
		memset(a,0,sizeof(a));
		memset(Edge,INF,sizeof(Edge));
		for(int i=0;i<m;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			if(Edge[v][u]>w)
				Edge[u][v]=Edge[v][u]=w;
		}
		for(int i=0;i<n; i++)
			Edge[i][i]=0;
			int pos;
			scanf("%d",&pos);
			printf("Case %d:\n",kk);
		Prim(pos);

		for(int i=0;i<n;i++)
		{
			if( i!=pos)
			{
				if(a[i])
					printf("%d\n",a[i]);
				else
					puts("Impossible");
			}
			else
				puts("0");
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-09

二 LightOJ 1002 最小生成树的相关文章

lightoj 1002 最小生成树

题意,给出若干条道路(m条)和若干个城市(n个,编号从0~n-1),给出一个起步城市k( 0<=k<=n) , 问所有其他城市到起步城市k的路径中,路径中最长的道路,最短可以 是多少. 分析,虽然一开始看错了题目,当作了最短路做,改了回来,用了并查集+队列拓展.但是Gealo说可以用dij做,数组保存的不是到某点的最短距离,而是到某点的最长的道路长为多少.好像也是可以的. 总之写的是最小生成树,那就用最小生成树写,最小生成树可以完美保证题意,题意中要找到路径,也就是要联通,且最小,符合最小生成

【LightOJ 1002】 Country Roads

[LightOJ 1002] Country Roads ...又一个另类OJ...最长路 贴个SPFA的 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <set> using namespace std; int mp[555][555]; int dis[555]; bool

lightoj 1029 最小生成树 + 最大生成树

题意,给出若干条连接两个屋子间的路线的价格(保证一定都能联通),问联通所有屋子的最大代价和最小代价的平均值为多少. 分析,即求一次最大生成树,一次最小生成树 1 /* When all else is lost the future still remains. */ 2 #define rep(X,Y,Z) for(int X=(Y);X<(Z);X++) 3 #define drep(X,Y,Z) for(int X=(Y);X>=(Z);X--) 4 #define fi first 5

Lightoj 1002 - Country Roads(prim算法)

I am going to my home. There are many cities and many bi-directional roads between them. The cities are numbered from 0 to n-1 and each road has a cost. There are m roads. You are given the number of my city t where I belong. Now from each city you h

[算法系列之二十七]Kruskal最小生成树算法

简介 求最小生成树一共有两种算法,一个是就是本文所说的Kruskal算法,另一个就是Prime算法.在详细讲解Kruskal最小生成树算法之前,让我们先回顾一下什么是最小生成树. 我们有一个带权值的图,我们要求找到一个所有生成树中具有最小权值的生成树.如下图所示,T是图G的生成树.但不是具有最小权值的生成树. 我们可以把他们想象成一组岛屿和连接它们的可能的桥梁.当然修桥是非常昂贵和费时的,所以我们必须要知道建设什么样的桥梁去连接各个岛.不过有一个重要的问题,建设这样一组连接所有岛屿的桥梁的最低价

hiho 1098 最小生成树二&#183;Kruscal算法 (最小生成树)

题目: 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 随着小Hi拥有城市数目的增加,在之间所使用的Prim算法已经无法继续使用了——但是幸运的是,经过计算机的分析,小Hi已经筛选出了一些比较适合建造道路的路线,这个数量并没有特别的大. 所以问题变成了——小Hi现在手上拥有N座城市,且已知其中一些城市间建造道路的费用,小Hi希望知道,最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达(假设有A.B.C三座城市,只需要在AB之间和BC之间建造道路,那么A

ACM第四站————最小生成树(普里姆算法)

对于一个带权的无向连通图,其每个生成树所有边上的权值之和可能不同,我们把所有边上权值之和最小的生成树称为图的最小生成树. 普里姆算法是以其中某一顶点为起点,逐步寻找各个顶点上最小权值的边来构建最小生成树. 其中运用到了回溯,贪心的思想. 废话少说吧,这个其实是一个模板,直接套用就好!直接上题吧!这些东西多练就好! 一.最小生成树: 题目描述 求一个连通无向图的最小生成树的代价(图边权值为正整数). 输入 第 一行是一个整数N(1<=N<=20),表示有多少个图需要计算.以下有N个图,第i图的第

白话数据结构之最小生成树

一:基本概念 1:什么是生成树? 对于图G<V,E>,如果其子图G'<V',E'>满足V'=V,且G'是一棵树,那么G'就是图G的一颗生成树.生成树是一棵树,按照树的定义,每个顶点都能访问到任何一个其它顶点.(离散数学中的概念),其中V是顶点,E是边,通俗来讲生成树必须包含原图中的所有节点且是连通的 比如 2:最小生成树 一个无向连通图G=(V,E),最小生成树就是联结所有顶点的边的权值和最小时的子图T,此时T无回路且连接所有的顶点,所以它必须是棵树.就是将原图的n个顶点用 n-1

计算最小生成树

一,什么是最小生成树 1,什么是生成树 如果连通图G的一个子图是一棵包含G所有顶点的树,则该子图成为G的生成树. 生成树是含有该连通图全部顶点的一个极小连通子图,它并不是唯一的,从不同的顶点出发可以得到不同的子树.含有N个顶点的连通图的生成树有N-1条边. 2,如何求一个连通图的生成树 要求一个连通图的生成树只需要从一个顶点出发,做一次深度优先或广度优先的搜索,将所经过的N个顶点和N-1条边连接起来,就形成了一个极小连通子图,也就是一棵生成树. 3,最小生成树 对一个带权的图,在一棵生成树中,各