图的分割

NC244459. 图的分割

描述

Lv学长最近沉迷于游戏《It Takes Two》，可惜他找不到女朋友，只能左手和右手一起玩。他对此非常不满，所以也想拆散别人。这不，现在他已经走火入魔了，连看到一个图都想把它拆成两部分。

现有无向图G，有n个节点，m条边，不存在重边或自环，所有点联通。

Lv学长想将原有图G拆分为两个联通的子图G1和G2。

具体来说，删除一些边，使得图G变为两个联通的子图G1和G2，G1和G2间没有边相连。需要保证删除边的边权最大值最小，在此基础上尽可能少地删除边。

请你输出被删除的边的边权中的最大值最小是多少。

输入描述

第一行2个正整数，n，m。
接下来m行，每行三个正整数x，y和v。表示x和y之间有一条权值为v的边相连。

输出描述

一行一个整数，表示删除边的边权最大值最小是多少。

示例1

输入:

输出:

说明:

需要删除1 4 2和2 3 1两条边，节点1，2为子图G1，节点3，4为子图G2，删除最大边权为2。输入较大，建议使用较快的输入方式。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 1220ms, 内存消耗: 4316K, 提交时间: 2022-11-05 15:32:18

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main()
{
    int a[1000009];
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y>>a[i];
    }
    sort(a+1,a+m+1);
    cout<<a[2]<<endl;
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1200ms, 内存消耗: 4348K, 提交时间: 2023-05-03 16:05:12

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,x,a[N];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x>>x>>a[i];
    }
    sort(a,a+m);
    cout<<a[1];
    return 0;
}

上一题

下一题

详情