A busy city

A busy city

Core ideas

As you can see from the title, n n n intersections are actually n n n vertices, the road is bidirectional, indicating that it is an undirected edge, which connects all intersections directly or indirectly, that is to say, in the end n n n nodes are connected, and the maximum score of the reconstructed roads should be as small as possible, that is, the edge weight of the selected roads should be as small as possible. From this information, we can know that this is similar to the meaning of minimum spanning tree? In fact, the topic also wants to require the largest side of the minimum spanning tree.

We know that for Kruskal algorithm, it sorts all edge weights from small to large, then selects from those with small edge weights, merges them to form a connected block, and finally gets a connected block containing n − 1 n-1 Connected blocks of n − 1 edges. Since the selected edge is selected from small to large, the last selected edge must be the largest edge in the minimum spanning tree (note that the reason is that Kruskal algorithm is greedy, and the edge weight is the smallest each time)

Therefore, we only need to run the following Kruskal algorithm, and then use the variable res to record each time we select an edge, that is r e s = w res=w res=w, the last selected edge is actually the largest edge in the minimum spanning tree.

Of course, this problem can also be solved by prim algorithm, that is, adding nodes every time S S When S sets, all r e s = m a x ( r e s , w ) res=max(res,w) res=max(res,w) until all nodes are added S S S set, then the final result r e s res res is the largest edge.

code

Writing method 1: Kruskal algorithm

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=310,M=8010;
int n,m;
struct Edge{
    int a,b,w;
    bool operator < (const Edge &W)const{
        return w<W.w;
    }
}edges[M];
int p[N];
int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}
void Kruskal()
{
    sort(edges,edges+m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    int res=0;
    for(int i=0;i<m;i++)
    {
        int a=find(edges[i].a);
        int b=find(edges[i].b);
        int w=edges[i].w;
        if(a!=b)
        {
            p[a]=b;
            //Because Kruskal algorithm has sorted the edge weight from small to large, the edge in the last selected minimum spanning tree
            //It must be the largest. Of course, it can also be written as res=max(res,w);
            res=w;
        }
    }
    //If the minimum spanning tree contains n points, there must be n-1 edges, so n-1 edges must be selected
    printf("%d %d\n",n-1,res);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    Kruskal();
    return 0;
}

prim algorithm

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=310,M=8010,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        // if(i&&dist[t])
        //     return INF;
        if(i)
            res=max(res,dist[t]);
        st[t]=true;
        for(int k=1;k<=n;k++)
            dist[k]=min(dist[k],g[t][k]);
    }
    return res;
}
int main()
{
    memset(g,0x3f,sizeof g);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    printf("%d %d\n",n-1,t);
    return 0;
}