Ngày 12-1-2019 - Bài 2

P2GRP - Tổng các đường đi ngắn nhất

Dữ liệu vào: standard input

Dữ liệu ra: standard output

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

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

Đăng bởi: namnguyen123

Quốc Vương Có Học muốn Mảnh Đất Trí Tuệ trở nên trí tuệ hơn. Vậy làm thế nào để trí tuệ? Trước tiên, trí tuệ
bắt đầu từ những thứ thân thuộc xung quanh chúng ta. Do vậy, chỉ cần thay đổi chúng, ta có thể trở nên trí tuệ
hơn (?). Có Học đã tìm ra một thứ thân thuộc với tất cả người dân mà chưa đạt tới trí tuệ tuyệt đối. Bạn có đoán
ra là gì không? Đó chính là đường đi, hay chính xác hơn là đường đi giữa các thành phố.
Tại Mảnh Đất Trí Tuệ, các thành phố đều được kết nối với nhau bằng những con đường hai chiều giữa chúng
(không có con đường nào nối một thành phố với chính nó và không có hai con đường cùng nối một cặp thành
phố). Quốc Vương Có Học quyết định hạ lệnh cho kĩ sư Đỉnh Cao phải thiết kế độ dài của các con đường một
cách trí tuệ, như thế mới làm đất nước trí tuệ lên được.
Sau nhiều ngày vắt óc, Đỉnh Cao nghĩ ra một thiết kế thật sự đỉnh cao: độ dài các con đường là một lũy thừa của
hai và đôi một khác nhau. Để kiểm chứng sự hiệu quả, Đỉnh Cao cần tính tổng các đường đi ngắn nhất giữa mọi
cặp thành phố và càng sớm càng tốt để yết kiến Quốc Vương.
Đỉnh Cao quyết định nhờ bạn tính hộ để anh còn kiểm tra lại sự đỉnh cao và trí tuệ của bản thiết kế. Liệu bạn có
thể tính thay Đỉnh Cao?
INPUT
Dòng đầu gồm hai số n, m tương ứng với số thành phố và số đường đi. 

m dòng sau, mỗi dòng ghi 3 số u , v , w  cho biết giữa 2 đỉnh u , v có cạnh trọng số 2^w
OUTPUT
In ra đáp án dưới dạng nhị phận . 

GIỚI HẠN
Tất cả các test có n ≤ 10⁵ , m  ≤  2 * 10⁵ ,  w < m . 

Nguồn bài : HSGSO 2017

 

Ví dụ

• input
  3 3
  1 2 0
  1 3 1
  2 3 2
  output
  110

Đường đi ngắn nhất (1 -> 3 ) : 2 , (2 -> 3) : 3 ; (1 -> 2) : 1 Tổng là 6 (110)

 

Lời giải:

using namespace std;
#include<bits/stdc++.h>
#define st first
#define nd second
#define FORE(i,a,b) for(int i=(a),b_=(b);i<=b_;++i)
#define FORD(i,a,b) for(int i=(a),b_=(b);i>=b_;--i)
#define TR(c, it) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)

const int MOD = 1e9 + 7 ;
const int MAXN = 1e5 + 5 ;
int par[MAXN], n , m ;
vector < pair < int, pair < int, int > > > Edeges, New ;
int findSet (int p)
{
    if (par[p] == p) return par[p] ;
    else return par[p] = findSet(par[p]) ;
}
void join (int u, int v)
{
    int x = findSet(u), y = findSet(v) ;
    par[y] = x ;
}
long long nChild[MAXN] ;
vector <int> g[MAXN] ;
void DFS (int u , int par )
{
    nChild[u] = 1 ;
    TR(g[u] , it)
    {
        int v = *it ;
        if (v == par) continue ;
        DFS(v , u) ;
        nChild[u] += nChild[v] ;
    }
}
long long ans[5 * MAXN] ;
int main()
{
#define TASK "NAME"
    // freopen(TASK".inp","r",stdin);
    // freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; ++i ) par[i] = i ;
    for(int i = 1 ; i <= m ; ++i )
    {
        int u, v, w ;
        cin >> u >> v >> w ;
        Edeges.push_back(make_pair(w , make_pair(u , v)) ) ;
    }
    sort(Edeges.begin(), Edeges.end() ) ;
    TR(Edeges , it)
    {
        int w = it -> st ;
        int u = (it -> nd).st ;
        int v = (it -> nd).nd ;
        if (findSet(u) == findSet(v) ) continue ;
        New.push_back(make_pair(w , make_pair(u , v))) ;
        join(u , v) ;
        g[u].push_back(v) ;
        g[v].push_back(u) ;
    }
    DFS(1 , -1) ;
    TR(New , it) {
        int w = it -> st ;
        int u = (it -> nd).st ;
        int v = (it -> nd).nd ;
        ans[w] += 1LL * (n - min(nChild[u] , nChild[v])) * min(nChild[u] , nChild[v]) ;
    }
    int sz = m - 1 ;
    for(int i = 0 ; i < m - 1 ; ++i ) ans[i + 1] += (ans[i] >> 1) , ans[i] = ans[i] & 1 ;
    while(1){
        if (ans[sz] > 1) {
            ans[sz + 1] += (ans[sz] >> 1 ) ;
            ans[sz] = ans[sz] & 1 ;
            sz ++ ;
        }
        else
            break ;
    }
    while(ans[sz] == 0)
        sz--;
    for(int i = sz ; i >= 0 ; --i )
    cout << ans[i] ;
    return 0;
}