- 传送门 -
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2768
| Root | 
|
(题面见pdf)
- 题意 -
求图中所有负环上的节点和可以到达负环的节点.
- 思路 -
第一次打负环,还不是很理解...
判负环的方法: 愚笨的我并没有从网上get到什么信息, 看来看去都是两句话: 当一个点入队超过n(节点数)时, 该节点在负环上(bfs), 当一个点在一条最短路径中出现两次时, 它在最短路径上(dfs).
然而我没有搞懂这两种方法与spfa, dfs, bfs的关系
要求可以到达负环的节点, 就要把边反向再对负环上的点进行bfs(dfs), 因为负环上的边全部反向不会影响整个负环, 所以我们可以只记录反向边, 然后直接当标准边来搞.
细节见代码.
PS:
dfs版的跑得比bfs版的快很多.
- 代码 -
bfs版:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1000 + 5;
const int M = 2000 + 5;
int TO[M], NXT[M], HD[N], V[M];
int DIS[N], CNT[N], INQ[N], QUE[N*N];
int DQUE[N];
bool OK[N];
int n, m, sz, cas;
void add(int x, int y, int val) {
TO[++sz] = y; NXT[sz] = HD[x]; HD[x] = sz; V[sz] = val;
}
void init() {
sz = 0;
memset(OK, false, sizeof (OK));
memset(HD, 0, sizeof (HD));
memset(CNT, 0, sizeof (CNT));
}
void bfs(int x) {
int head = 0, tail = 0;
DQUE[++tail] = x;
while (head < tail) {
int p = DQUE[++head];
if (OK[p]) continue;
OK[p] = true;
for (int i = HD[p]; i; i = NXT[i])
if (!OK[TO[i]]) DQUE[++tail] = TO[i];
}
}//找到一个位于负环上的节点时, 搜索所有可以到达它的节点
void spfa_bfs() {
int head = 0, tail = 0;
for (int i = 0; i < n; ++i) {
DIS[i] = 0;
QUE[++tail] = i;
INQ[i] = 1;
}
while (head < tail) {
int p = QUE[++head];
INQ[p] = 0;
if (OK[p]) continue;
for (int i = HD[p]; i; i = NXT[i]) {
int v = TO[i];
if (DIS[v] > DIS[p] + V[i] && !OK[v]) {
DIS[v] = DIS[p] + V[i];
if (!INQ[v]) {
INQ[v] = 1;
QUE[++tail] = v;
if (++CNT[v] > n)
bfs(v); //统计每个点的入队次数
}
}
}
}
}
int main() {
scanf("%d", &cas);
for (int i = 1; i <= cas; ++i) {
printf("Case %d:", i);
init();
scanf("%d%d", &n, &m);
while (m--) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
add(y, x, k);
}
spfa_bfs();
int ans = 1;
for (int i = 0; i < n; ++i)
if (OK[i]) {
ans = 0;
printf(" %d", i);
}
if (ans) printf(" impossible");
printf("
");
}
return 0;
}
dfs版:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1000 + 5;
const int M = 2000 + 5;
int TO[M], NXT[M], HD[N], V[M];
int DIS[N], VIS[N];
int DQUE[N];
bool OK[N];
int n, m, sz, cas;
void add(int x, int y, int val) {
TO[++sz] = y; NXT[sz] = HD[x]; HD[x] = sz; V[sz] = val;
}
void init() {
sz = 0;
memset(OK, false, sizeof (OK));
memset(HD, 0, sizeof (HD));
}
void bfs(int x) {
int head = 0, tail = 0;
DQUE[++tail] = x;
while (head < tail) {
int p = DQUE[++head];
if (OK[p]) continue;
OK[p] = true;
for (int i = HD[p]; i; i = NXT[i])
if (!OK[TO[i]]) DQUE[++tail] = TO[i];
}
}
void spfa_dfs(int x) {
VIS[x] = 1;
for (int i = HD[x]; i; i = NXT[i]) {
int v = TO[i];
if (OK[v]) continue;
if (DIS[v] > DIS[x] + V[i])
if (VIS[v]) {
bfs(v);
break; //这里写break可以使VIS数组归0而不需要每次初始化
}
else {
DIS[v] = DIS[x] + V[i];
spfa_dfs(v);
}
}
VIS[x] = 0;
}
int main() {
scanf("%d", &cas);
for (int i = 1; i <= cas; ++i) {
printf("Case %d:", i);
init();
scanf("%d%d", &n, &m);
while (m--) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
add(y, x, k);
}
for (int i = 0; i < n; ++i) {
memset(DIS, 0x3f, sizeof (DIS));
DIS[i] = 0;
if (!OK[i]) spfa_dfs(i);
}
int ans = 1;
for (int i = 0; i < n; ++i)
if (OK[i]) {
ans = 0;
printf(" %d", i);
}
if (ans) printf(" impossible");
printf("
");
}
return 0;
}