HDU - 5876 Sparse Graph 补图最短路(使用两个set的做法)

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

给出图G,求图G的补图H对于源点S的单源最短路


题解

这道题目就是稍微考虑一下就可以了。同样是一个BFS的写法,只不过这次的BFS要求不能使用图中给出的边,我们要求的是补图的最短路,就要用非原图的所有边。
这样我们可以使用两个set,其中过一个记录当前会被更新的点,另一个记录还没有被更新过的点。具体实现看代码,不好解释。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
sets1;
sets2;
const int maxn = 2e5+5;
struct edge{
    int to,next;
}e[maxn];
int h[maxn];
int dis[maxn];
int T,n,m,S,u,v,cnt;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (((num<<2)+num)<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
void init(){
    for(int i = 1;i <= n;++i){
        h[i] = -1;
        dis[i] = -1;
    }
    cnt = 0;
}
void add(int u,int v){
    e[cnt].to = v;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void BFS(int s){
    for(int i = 1;i <= n;++i){
        if(i == s)continue;
        s1.insert(i);
    }
    queueq;
    dis[s] = 0;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = h[x];i != -1;i = e[i].next){
            int v = e[i].to;
            if(!s1.count(v))continue;
            s1.erase(v);
            s2.insert(v);
        }
        for(set::iterator it = s1.begin();it != s1.end();++it){
            q.push(*it);
            dis[*it] = dis[x]+1;
        }
        s1.swap(s2);
        s2.clear();
    }
    return;
}
int main(){
    T = get_num();
    while(T--){
        n = get_num();
        m = get_num();
        init();
        for(int i = 1;i <= m;++i){
            u = get_num();
            v = get_num();
            add(u,v);
            add(v,u);
        }
        S = get_num();
        BFS(S);
        for(int i = 1;i <= n;++i){
            if(i == S)continue;
            if(i < n)printf("%d ",dis[i]);
            else printf("%d\n",dis[i]);
        }
    }
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00