VOSNET – spoj

Đề bài:

Thuật toán:

  • Nhận xét, sau mỗi ngày khoảng cách giữa 2 đỉnh bất kì giảm đi nửa.
  • Gọi a[u][v] là khoảng cách ngắn nhất từ đỉnh u -> v (tính trong O(n * (n + m)) )
    Thời gian đi từ u -> v = k bé nhất sao cho 2 ^ k >= a[u][v]. (dùng toán tính trong O(1))
    => O(n * (n + m) + n * n)

Code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 3333;
 
int n, m;
int a[N][N], ans[N];
vector <int> adj[N];
 
void bfs(int r) {
    queue <int> q;
    q.push(r);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (v != r && !a[r][v]) {
            a[r][v] = a[r][u] + 1;
            //cerr << r << " " << v << " " << a[r][v] << "\n";
            q.push(v);
        }
    }
}
 
int main() {
//    freopen("input.in", "r", stdin);
  //  freopen("output.out", "w", stdout);
 
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    //bfs(2);
    for (int i = 1; i <= n; ++i) bfs(i);
 
    for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) if (a[i][j] != 0) {
        int k = log2(a[i][j]);
        k += 1ll << k != a[i][j]; //cerr << i << " " << j << " " << a[i][j] << " " << k << "\n";
        ans[k]++;
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d ", ans[i]);
        if (ans[i] == 0) break;
    }
 
    return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*