Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký
Thảo luận
Thảo luận
PATH - Đường đi ngắn thứ k

Hướng dẫn bài PATH - Đường đi ngắn thứ k

Nguyễn Hoàng Sơn 2021-08-11 7:47:55 2021-10-15 1:48:34

Nguồn solution by Sơn đẹp zai quá: https://hotavn.com/solution-path-duong-di-ngan-thu-k_103194.html?group=7

Ý tưởng

Ta nhận thấy rằng đồ thị khá to với 10^5 đỉnh, cạnh nên nếu ta trâu tìm tất cả đường đi thì sẽ mất O(n^3) , nếu tối ưu hơn thì mắt O(n*m* \log_2 {(n*m)}) vẫn quá lớn chỉ qua được 2 sub đầu là 50\% số điểm

Ta nhận thấy rằng k \le 10^3 khá bé nên ta sẽ tìm cách giải có độ phức tạp theo k

Ta nhận thấy có một cách tìm một đường đi ngắn nhất trong một đồ thị bất kỳ rất dễ, ta chỉ việc kiểm tra tất các cạnh trong O(m) vì đồ thì này không có trọng số âm,ta gọi w_i là độ dài cạnh i không mất tính tổng quát ta có w_0 + w_1 + ... + w_n > min(w_0, w_1, ..., w_n) . Theo bất đẳng thức trên thì để tìm đường đi nhỏ nhất trong một đồ thị ta chỉ việc tìm cạnh có độ dài nhỏ nhất.

Từ nhận xét trên ta có thể suy ra cạnh nhỏ thứ k chắc chắc nằm trong một tập hợp gồm k cạnh nhỏ nhất hoặc đường đi con chứa ít nhất 1 cạnh trong số k cạnh nhỏ nhất ban đầu

Vì thế nên ta đã giới giạn số cạnh cần xử lý trong khoảng k .

Trong lúc thao tác mở rộng đường đi ta có thể sử dụng cấu trúc set để tránh đường đi bị trùng và thêm trong O(log2(max(k)))

Giải thích solution

//Khai báo mảng vector để chứa cạnh theo đỉnh
struct edge{
    int v;
    ll w;
};
vector<edge> ed[100005];

//Khai báo dữ liệu đại diện cho đường đi và đặc trưng bởi 2 đầu xuất phát và kết thúc
struct mypath{
    int u, v;
    ll w;
};
//Luôn đảm bảo rằng ax.u < ax.v để tránh đường đi bị trùng
void Tformat(mypath &ax){
    if(ax.u > ax.v) swap(ax.u, ax.v);
}

//Khai báo set lưu các đường đi
struct cmp{
    bool operator() (const mypath &ax, const mypath &bx) const{
        if(ax.u != bx.u) return ax.u < bx.u;
        return ax.v < bx.v;
    }
};
set<mypath, cmp> paths;

//Lấy đường đi dài nhất trong tất cả các đường đi trong paths
ll getmaxpath(){
    ll ans = 0;
    for(auto j = paths.begin(); j!=paths.end(); j++) ans = max(ans, (*j).w);
    return ans;
}

/*
Kiểm tra xem đường đi ax đã có trong paths chưa, nếu chưa thì thêm.
Nếu có rồi thì kiểm tra xem đường đi mới có tối ưu hơn không, nếu có thì thêm vào paths
*/
void faddtruepath(mypath ax){
    auto it = paths.find(ax);
    if(it == paths.end()) paths.insert(ax);
    else{
        mypath tit = (*it);
        if(tit.w > ax.w){
            paths.erase(it);
            paths.insert(ax);
        }
    }
}

/*
Gọi đường đi dài nhất trong paths là maxWay
Mở rộng đường đi, thêm bất kỳ đường đi mới nào nếu paths.size() < k đồng thời lấy cập nhật maxWay với độ dài đường đi mới thêm đó
Ta thêm đường đi mới bằng cách chọn 1 trong 2 đầu của đường đi ta đang xét rồi từ đỉnh ta chọn ta đi tới đỉnh mới
Nếu paths.size() >= k thì chỉ thêm đường đi mới khi độ dài đường đi mới đó < maxWay

Lưu ý: khi thêm đường đi mới ta nên thêm nháp vào một vector trước để tránh trường hợp bị xử lý cả các cạnh mới thêm
*/
void addpath(bool ok){
    ll maxx = getmaxpath();
    for(auto j = paths.begin(); j!=paths.end(); j++){
        mypath i = (*j);
        for(auto &v: ed[i.u]){
            mypath newpath = {i.v, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(paths.size() < k) maxx = max(newpath.w, maxx);
            if((newpath.w < maxx && paths.size() >= k) || paths.size()<k || !ok) pathsbeta.push_back(newpath);
        }
        if(i.u != i.v) for(auto &v: ed[i.v]){
            mypath newpath = {i.u, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(paths.size() < k) maxx = max(newpath.w, maxx);
            if((newpath.w < maxx && paths.size() >= k) || paths.size()<k || !ok) pathsbeta.push_back(newpath);
        }
    }
    for(auto i: pathsbeta) faddtruepath(i);
}

/*
Gọi đường đi dài nhất trong paths là maxWay
kiểm tra xem còn cách tạo đường đi nào có độ dài < maxWay nữa không
*/
bool check(){
    if(paths.size() < k) return true;
    ll maxx = getmaxpath();
    for(auto j = paths.begin(); j!=paths.end(); j++){
        mypath i = (*j);
        for(auto &v: ed[i.u]){
            mypath newpath = {i.v, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(newpath.w < maxx && paths.find(newpath) == paths.end()) return true;
        }
        if(i.u != i.v) for(auto &v: ed[i.v]){
            mypath newpath = {i.u, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(newpath.w < maxx && paths.find(newpath) == paths.end()) return true;
        }
    }
    return false;
}

/*
Xóa các đường đi có u == v
*/
void dele(){
    for(int i = 1; i\leq n; i++){
        if(ed[i].size() > 0){
            paths.erase({i,i,0});
        }
    }
}

/*
Nếu sau khi thêm cạnh mà paths.size() > k
thì ta sẽ sort lại các đường đi paths theo độ dài đường đi
rồi xóa các đường đi dài nhất cho đến khi paths.size() <= k
Đồng thời ta cập nhật kết quả là thằng paths ở vị trí thứ k
*/
void getonlymin(){
    if(paths.size() < k) return;
    pathsbeta.clear();
    for(auto j = paths.begin(); j != paths.end(); j++){
        mypath i = (*j);
        pathsbeta.push_back(i);
    }
    sort(pathsbeta.begin(), pathsbeta.end(), [](mypath &ax, mypath &bx){
        return ax.w < bx.w;
    });
    while (pathsbeta.size() > k) pathsbeta.pop_back();
    res = pathsbeta.back().w;
    paths.clear();
    for(auto i: pathsbeta) paths.insert(i);
}

Code one punch AC

//Hoang Son WIBU lolicon codeforces rate 1642 khong cay
#include <bits/stdc++.h>
#define F first
#define S second
#define times double stime = clock();
#define gettime cerr << "\nTime executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n";
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
const ll mod = 1000000007;

int n, m, k;
struct edge{
    int v;
    ll w;
};
vector<edge> ed[100005];
struct mypath{
    int u, v;
    ll w;
};
void Tformat(mypath &ax){
    if(ax.u > ax.v) swap(ax.u, ax.v);
}
vector<mypath> pathsbeta;

//Set
struct cmp{
    bool operator() (const mypath &ax, const mypath &bx) const{
        if(ax.u != bx.u) return ax.u < bx.u;
        return ax.v < bx.v;
    }
};
set<mypath, cmp> paths;
//end set

ll getmaxpath(){
    ll ans = 0;
    for(auto j = paths.begin(); j!=paths.end(); j++) ans = max(ans, (*j).w);
    return ans;
}
void faddtruepath(mypath ax){
    auto it = paths.find(ax);
    if(it == paths.end()) paths.insert(ax);
    else{
        mypath tit = (*it);
        if(tit.w > ax.w){
            paths.erase(it);
            paths.insert(ax);
        }
    }
}
void addpath(bool ok){
    ll maxx = getmaxpath();
    for(auto j = paths.begin(); j!=paths.end(); j++){
        mypath i = (*j);
        for(auto &v: ed[i.u]){
            mypath newpath = {i.v, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(paths.size() < k) maxx = max(newpath.w, maxx);
            if((newpath.w < maxx && paths.size() >= k) || paths.size()<k || !ok) pathsbeta.push_back(newpath);
        }
        if(i.u != i.v) for(auto &v: ed[i.v]){
            mypath newpath = {i.u, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(paths.size() < k) maxx = max(newpath.w, maxx);
            if((newpath.w < maxx && paths.size() >= k) || paths.size()<k || !ok) pathsbeta.push_back(newpath);
        }
    }
    for(auto i: pathsbeta) faddtruepath(i);
}
bool check(){
    if(paths.size() < k) return true;
    ll maxx = getmaxpath();
    for(auto j = paths.begin(); j!=paths.end(); j++){
        mypath i = (*j);
        for(auto &v: ed[i.u]){
            mypath newpath = {i.v, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(newpath.w < maxx && paths.find(newpath) == paths.end()) return true;
        }
        if(i.u != i.v) for(auto &v: ed[i.v]){
            mypath newpath = {i.u, v.v, i.w + v.w};
            if(newpath.u == newpath.v) continue;
            Tformat(newpath);
            if(newpath.w < maxx && paths.find(newpath) == paths.end()) return true;
        }
    }
    return false;
}

ll res = 0;
void dele(){
    for(int i = 1; i\leq n; i++){
        if(ed[i].size() > 0){
            paths.erase({i,i,0});
        }
    }
}
void getonlymin(){
    if(paths.size() < k) return;
    pathsbeta.clear();
    for(auto j = paths.begin(); j != paths.end(); j++){
        mypath i = (*j);
        pathsbeta.push_back(i);
    }
    sort(pathsbeta.begin(), pathsbeta.end(), [](mypath &ax, mypath &bx){
        return ax.w < bx.w;
    });
    while (pathsbeta.size() > k) pathsbeta.pop_back();
    res = pathsbeta.back().w;
    paths.clear();
    for(auto i: pathsbeta) paths.insert(i);
}

void process(){
    int tcase = 1;
    //cin >> tcase;
    while(tcase--){
        cin >> n >> m >> k;
        for(int i = 1; i\leq m; i++){
            int u, v, w;
            cin >> u >> v >> w;
            ed[u].push_back({v, w});
            ed[v].push_back({u, w});
        }
        paths.clear();
        for(int i = 1; i\leq n; i++){
            if(ed[i].size() > 0){
                paths.insert({i,i,0});
            }
        }
        addpath(false);
        dele();
        getonlymin();
        while(check()){
            addpath(true);
            getonlymin();
        }
        cout << res << endl;
    }
}

int online = 2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (online == 0) {
        freopen("in.inp", "r", stdin);
        freopen("out.out", "w", stdout);
    } else if (online == 1) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    // times
    process();
    // gettime
    return 0;
}
Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS