http://acm.hdu.edu.cn/showproblem.php?pid=5876
Sparse Graph
Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N−1 other vertices.
题意:给出一个图,和一个起点,求在该图的补图中从起点到其他N-1个点的最短距离。如果不连通输出-1.
思路:比赛的时候觉得这题N那么大不会做。现在回过头发现貌似不难。用set将未走过的点放置进去,并在对点的邻边进行扩展的时候,把能走到的邻点删除掉(即补图中可以走到的邻点保留)。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
using namespace std;
#define N 200010
#define INF 0x3f3f3f3f struct node
{
int v, nxt;
}edge[N];
int head[N];
int d[N], tot; void add(int u, int v)
{
edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;
edge[tot].v = u; edge[tot].nxt = head[v]; head[v] = tot++;
} void bfs(int st, int n)
{
queue<int> que;
d[st] = ;
que.push(st);
set<int> s1, s2;
for(int i = ; i <= n; i++) {
if(i != st) s1.insert(i);
}
while(!que.empty()) {
int u = que.front(); que.pop();
for(int k = head[u]; ~k; k = edge[k].nxt) {
int v = edge[k].v;
if(!s1.count(v)) continue;
s1.erase(v); //补图中当前能走到的并且还未更新过的
s2.insert(v); //补图中走不到的还要扩展的
}
for(set<int>:: iterator it = s1.begin(); it != s1.end(); it++) {
d[*it] = d[u] + ;
que.push(*it);
}
s1.swap(s2); //还没更新过的
s2.clear();
}
} int main()
{
int t;
scanf("%d", &t);
while(t--) {
memset(head, -, sizeof(head));
memset(d, INF, sizeof(INF));
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
int st;
scanf("%d", &st);
bfs(st, n);
bool f = ;
for(int i = ; i <= n; i++) {
if(i != st) {
if(f) printf(" ");
f = ;
if(d[i] == INF) printf("-1");
else printf("%d", d[i]);
}
}
puts("");
} return ;
}
HDU 5876:Sparse Graph(BFS)的更多相关文章
-
HDU - 5876 :Sparse Graph (完全图的补图的最短路 -BFS&;set)
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinc ...
-
HDU 1728:逃离迷宫(BFS)
http://acm.hdu.edu.cn/showproblem.php?pid=1728 逃离迷宫 Problem Description 给定一个m × n (m行, n列)的迷宫,迷宫中有 ...
-
HDU.2612 Find a way (BFS)
HDU.2612 Find a way (BFS) 题意分析 圣诞节要到了,坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车.百度地图一下,发现周围的召唤师大峡谷还不少,这对基佬纠结着,该去哪一个...坤 ...
-
HDU 4635:Strongly connected(强连通)
http://acm.hdu.edu.cn/showproblem.php?pid=4635 题意:给出n个点和m条边,问最多能添加几条边使得图不是一个强连通图.如果一开始强连通就-1.思路:把图分成 ...
-
九度OJ 1335:闯迷宫 (BFS)
时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:1782 解决:483 题目描述: sun所在学校每年都要举行电脑节,今年电脑节有一个新的趣味比赛项目叫做闯迷宫. sun的室友在帮电脑节设计 ...
-
题解报告:hdu 2717 Catch That Cow(bfs)
Problem Description Farmer John has been informed of the location of a fugitive cow and wants to cat ...
-
HDU 2717 Catch That Cow (bfs)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2717 Catch That Cow Time Limit: 5000/2000 MS (Java/Ot ...
-
HDU 1890:Robotic Sort(Splay)
http://acm.hdu.edu.cn/showproblem.php?pid=1890 题意:有一个无序序列,经过不断地翻转,使得最后的序列是一个升序的序列,而且如果相同数字要使在原本序列靠前的 ...
-
HDU 2767:Proving Equivalences(强连通)
http://acm.hdu.edu.cn/showproblem.php?pid=2767 题意:给出n个点m条边,问在m条边的基础上,最小再添加多少条边可以让图变成强连通.思路:强连通分量缩点后找 ...
随机推荐
-
Angular指令渗透式理解
通过一段时间对angular指令的使用,理解了angular指令的意义,下面逐一介绍一下. ng-app:定义一个angualr模块,表示angular作用的范围,如下代码: ng-app在html标 ...
-
I2C总线模拟(郭天祥视屏)
电路图 思路 1.向EEPROM中通过I2C总线写入一个字节 2.通过I2C总线读出写入的字节 3.如果写入和读出成功点亮发光二极管 程序 #include <REGX51.H> #def ...
-
python3之异常处理,断言和反射
1.异常基础 python在运行过程中,程序解释机制会测试代码,如检测不通过则会抛出异常. try: aa = 10 bb = ' cc = aa + bb except Exception as e ...
-
Linux以GB显示内存大小
Linux以GB显示内存大小 youhaidong@youhaidong-ThinkPad-Edge-E545:~$ free -g total used free shared buffers ca ...
-
struts2 可以用ognl拿到值而不可以用el拿到值的解决方法
错误debug后 得到了There is no read method for container的错误 于是我new了一个实体类 package com.unity; public class St ...
-
css的overflow属性
原文:https://www.jianshu.com/p/67b536fc67c1 ------------------------------------------- 事实上我挺长一段时间都没弄清 ...
-
Linux实现多线程高速下载
使用Wget下载,有时候速度挺慢的. 有没有好办法呢? 一.解决方案 安装axel 安装方法: yum -y install epel-release .el7.x86_64.rpm rpm -ivh ...
-
express session
一.什么是session? 最近在学习node.js 的express框架,接触到了关于session方面的内容.翻阅了一些的博客,学到了不少东西,发现一篇博文讲的很好,概念内容摘抄如下: Sessi ...
-
Maven Compilation error [package org.testng.annotations does not exist]
背景 在执行mvn test的时候,提示package org.testng.annotations does not exist 解决办法 Open pom.xml file. Go to &quo ...
-
按位与&;、按位或|、按位异或^
与1进行位与&运算,值保持不变: 与0进行位与&运算,值清0: 按位与&常用于将整型变量中某些位清0,而其他位保持不变. 与1进行位或|运算,值置1: 与0进行位或|运算,值保 ...