The Best Path ----HDU - 5883 （补图最短路）

62 阅读 0 评论 41 点赞

我是靠谱客的博主背后乌冬面，最近开发中收集的这篇文章主要介绍The Best Path ----HDU - 5883 （补图最短路），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=5883

题目要求求一个图G的补图的各点最短路

想到先存图，然后推补图

点的范围很大，用邻接矩阵显然存不下，如果用邻接表，，时间可能会超。。

之后经过看大佬题解，终于理解。

开两个set集合，把此时能到达的节点存进去，和不能到达的点存进去。。。不断维护这两个set

补图概念，原图有的边，补图中肯定没有

比如，此时NOW点能到达的点集合，，这个集合的补集，就是now在补图中能到达的点，这样就能通过此时得到的set直接bfs最短路

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#define
N 1000008
using namespace std;
queue<int>
que;
set<int> ac,nac;
vector<int> g[N];
int n,dis[N];
void solve(int s)
{
memset(dis, 0, sizeof(dis));
while (!que.empty()) que.pop();
ac.clear(),nac.clear();
que.push(s);
for(int i=1;i<=n;i++)
{
if(s!=i) ac.insert(i);
}
while (!que.empty()) {
int x=que.front();
que.pop();
for(int i=0;i<g[x].size();i++)
{
if(!ac.count(g[x][i]))continue;
nac.insert(g[x][i]);
ac.erase(g[x][i]);
}
for(set<int>::iterator i=ac.begin();i!=ac.end();i++)
{
dis[*i]=dis[x]+1;
que.push(*i);
}
ac.swap(nac);
nac.clear();
}
int f=0;
for(int i=1;i<=n;i++)
{
if(i!=s)
{
if(f) printf(" ");
if(dis[i]!=0)
printf("%d",dis[i]);
else printf("-1");
f=1;
}
}
cout<<endl;
}
int main()
{
int T,m,be,en;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
g[i].clear();
for(int i=0;i<m;i++)
{
cin>>be>>en;
g[be].push_back(en);
g[en].push_back(be);
}
int s;
cin>>s;
solve(s);
}
return 0;
}