Ngày 11-1-2019 - Bài 3

SMINROAD - Đường đi trọng số nhỏ nhất

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 2.0 giây

Giới hạn bộ nhớ: 256 megabyte

Đăng bởi: namnguyen123

Cho đồ thị vô hướng n đỉnh , m cạnh . Trên mỗi đỉnh của đồ thị , có gắn một số tượng trưng cho giá trị của đỉnh đó . Trọng số của một đường đi chính bằng giá trị nhỏ nhất của các đỉnh thuộc đường đi đó . F(u , v) là giá trị lớn nhất trong của trọng số của các đường đi từ u -> v .

Yêu cầu : Tính tổng các F(u , v) với (u # v) .

INPUT :

Dòng đầu tiên gồm 2 số nguyên dương n , m ( n < 10⁵  , m < 2.10⁵ ) . 

Dòng thứ 2 gồm n số là giá trị các đỉnh : a₁ , a₂ , .. , a_n . ( 0 < a_i < 10⁹ ). 

m dòng tiếp theo là các cạnh đồ thị . Mỗi dòng gồm 2 số nguyên dương u , v ( 1 < u , v < n ). 

OUTPUT : 

Kết quả bài toán . 

Ví dụ

• input
  4 3
  10 20 30 40
  1 3
  2 3
  4 3
  output
  200

• u = 1 ,  v = 3 ,  F(u , v)  = 10.
• u = 2 ,  v = 3 ,  F(u , v)  = 20.
• u = 4 ,  v = 3 ,   F(u , v)  = 30.
• u = 1 ,  v = 2 ,   F(u , v)  = 10.
• u = 2 ,  v = 4 ,   F(u , v)  = 20.
• u = 4 ,  v = 1 ,   F(u , v)  = 10.

​Tổng là 100 x 2 = 200 . 

Lời giải:

#include <bits/stdc++.h>
using namespace std;
long long kq,k;
int sl[100001],r[100001],n,m,i,u,v,c[100001],r1,r2,d;
struct pt
{
    int u,v,k;
};
pt a[200001];
bool cmp(pt a,pt b)
{
    return a.k>b.k;
}
int root(int u)
{
    if(u==r[u]) return u;
    r[u]=root(r[u]);
    return r[u];
}
void hop(int u,int v)
{
    int s1=sl[u],s2=sl[v];
    kq+=s1*s2*k;
    if(s1>s2)
    {
        r[v]=u;
        sl[u]=s1+s2;
    }
    else
    {
        r[u]=v;
        sl[v]=s1+s2;
    }
}
int main()
{
    //freopen("ntu.inp","r",stdin);
    //freopen("ntu.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        r[i]=i; sl[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        a[i]={ u,v,min(c[u],c[v]) };
    }
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        u=a[i].u; v=a[i].v; k=a[i].k;
        r1=root(u); r2=root(v);
        if(r1==r2) continue;
        hop(r1,r2); d++;
        if(d==n-1) break;
    }
    printf("%lld",2*kq);
}