Bakery

发表于

  • 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。

  • 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。

  • 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。

  • 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。

  • 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

    1.Kruskal算法

    此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
    \1. 把图中的所有边按代价从小到大排序；
    \2. 把图中的n个顶点看成独立的n棵树组成的森林；
    \3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
    \4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

    2.Prim算法

    此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

    1. 图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
    2. 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
    3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

    由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息。

    Bakery

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    #include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    const int maxn = 1e5+7;
    int a[maxn];
    int vis[maxn];
    vector<pair<int,LL> >e[maxn];//pair是将2个数据组合成一组数据
    int main()
    {
    	int n,m,k;//城市，道路，仓库
    	LL ans = 1e18;
    	cin>>n>>m>>k;
    	for(int i = 1;i<=m;i++)
    	{
    		int u,v;
    		LL w;
    		scanf("%d%d%lld",&u,&v,&w);
    		e[u].push_back(make_pair(v,w));
    		e[v].push_back(make_pair(u,w));
    	}
        if(!k)
    	{
    		cout<<-1<<endl;
    		return 0;
    	}
    	else if(k==n)
    	{
    		cout<<-1<<endl;
    		return 0;
    	}
    	for(int i = 1;i<=k;i++)
    		scanf("%d",&a[i]),vis[a[i]]=1;//标记仓库
    	for(int u = 1;u<=n;u++)
    	{
    	   // cout<<e[u].size();
    		if(vis[u])continue;
            for(int i = 0;i<e[u].size();i++)
            {

                int v = e[u][i].first;//找到与此点相连的点
    			LL w = e[u][i].second;//距离
    //			cout<<e[2][2].first;
    //			cout<<e[2][2].second;
    //			break;
              //cout<<v<<" "<<w<<endl;
    			if(vis[v])
    				ans = min(ans,w);
    		}

    	}
    	if(ans==1e18)
    		cout<<-1<<endl;
    	else
    		cout<<ans<<endl;
    }