首页 > 代码库 > [HDOJ5876]Sparse Graph（补图最短路）
[HDOJ5876]Sparse Graph（补图最短路）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5876
题意：求一个图的补图中的单源最短路。
题解说：补图上的 BFS 是非常经典的问题。一般的做法是用链表（或者偷懒用 std::set）维护还没 BFS 过的点。当要扩展点 u 的时候，遍历一次还没访问过的点 v，如果 uv 没边，那么将 v 入队。否则将 v 留在未扩展点中。很明显，后者只会发生 m 次，前者只会发生 n 次，所以复杂度是 O(n + m)。
总得说，求补图的最短路就是要存原图，并且需要有一个额外的set来维护未扩展的点集合。
在bfs的时候从队列取出一个点u，访问该点u邻接的点v，假如uv之间有边则补图无边，否则v会入队。
最后的时候要把入队的点从未扩展点集合中删掉。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 using namespace std; 20 #define fr first 21 #define sc second 22 #define cl clear 23 #define BUG puts("here!!!") 24 #define W(a) while(a--) 25 #define pb(a) push_back(a) 26 #define Rint(a) scanf("%d", &a) 27 #define Rll(a) scanf("%I64d", &a) 28 #define Rs(a) scanf("%s", a) 29 #define Cin(a) cin >> a 30 #define FRead() freopen("in", "r", stdin) 31 #define FWrite() freopen("out", "w", stdout) 32 #define Rep(i, len) for(int i = 0; i < (len); i++) 33 #define For(i, a, len) for(int i = (a); i < (len); i++) 34 #define Cls(a) memset((a), 0, sizeof(a)) 35 #define Clr(a, x) memset((a), (x), sizeof(a)) 36 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 37 #define lrt rt << 1 38 #define rrt rt << 1 | 1 39 #define pi 3.14159265359 40 #define RT return 41 #define lowbit(x) x & (-x) 42 #define onecnt(x) __builtin_popcount(x) 43 typedef long long LL; 44 typedef long double LD; 45 typedef unsigned long long ULL; 46 typedef pair<int, int> pii; 47 typedef pair<string, int> psi; 48 typedef pair<LL, LL> pll; 49 typedef map<string, int> msi; 50 typedef vector<int> vi; 51 typedef vector<LL> vl; 52 typedef vector<vl> vvl; 53 typedef vector<bool> vb; 54 55 const int maxn = 200200; 56 const int inf = 10000010; 57 set<int> G[maxn]; 58 set<int> x; 59 int n, m, s; 60 int d[maxn]; 61 62 void bfs(int s) { 63 Clr(d, -1); 64 d[s] = 0; 65 queue<int> q; 66 q.push(s); x.erase(s); 67 set<int>::iterator v; 68 while(!q.empty()) { 69 int u = q.front(); q.pop(); 70 set<int> y; 71 for(v = x.begin(); v != x.end(); v++) { 72 if(G[u].find(*v) == G[u].end()) { 73 if(d[*v] == -1) d[*v] = d[u] + 1; 74 else d[*v] = min(d[*v], d[u] + 1); 75 y.insert(*v); 76 q.push(*v); 77 } 78 } 79 for(v = y.begin(); v != y.end(); v++) { 80 x.erase(*v); 81 } 82 } 83 } 84 85 int main() { 86 // FRead(); 87 int T, u, v; 88 Rint(T); 89 W(T) { 90 Rint(n); Rint(m); 91 x.clear(); 92 For(i, 1, n+1) { 93 x.insert(i); 94 G[i].clear(); 95 } 96 Rep(i, m) { 97 Rint(u); Rint(v); 98 G[u].insert(v); G[v].insert(u); 99 }100 Rint(s);101 bfs(s);102 For(i, 1, n+1) {103 if(i == s) continue;104 printf("%d%c", d[i], i == n ? ‘\n‘ : ‘ ‘);105 }106 }107 RT 0;108 }
[HDOJ5876]Sparse Graph（补图最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。