poj 3114 Countries in War

本文从WordPress迁移而来, 查看全部WordPress迁移文章

强连通分量 + 最短路

题意:城市间通信,给出n,n个城市,m,m条边,分别是端点和权,如果两个城市属于同一个国家,那么他们的通信时间为0,否则则按边权算一次的通信时间。两个城市被认为在一个国家,是从A能到B,从B也能到A。下面给出K个查询,能从u到v传递信息,需要多少时间,如果从u无法传递到v,输出那个长长的英文句子

其实就是一个最短路,但是最短路的边权有讲究,虽然给出了u,v,w,但是u和v可能是同一个国家的,那么w应该是0而不是原来的值,所以要怎么判断u和v是不是在同一个国家,也就是他们可以互达,很明显不能查询一次判断一次,而是应该先搞出强连通分量,属于同一个强连通分量的两点间的边权为0

这题不难,很直白,tarjan,和各种最短路的算法老实打就是了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
//强连通分量+最短路
//属于一个强连通分量的点,路径为0,否则按原边权

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 510
#define M 250010
#define INF 0x3f3f3f3f
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int n,tot;
int head[N];
struct edge
{
int u,v,w,next;
}e[M];
int dfn[N] , low[N] , belong[N] , dcnt , bcnt;
int stack[N] , top;
bool ins[N];
int d[N][N];
bool solve[N];

void add(int u ,int v ,int w ,int k)
{
e[k].u = u; e[k].v = v; e[k].w = w;
e[k].next = head[u]; head[u] = k;
}

void tarjan(int u)
{
stack[++top] = u;
ins[u] = true;
dfn[u] = low[u] = ++dcnt;
for(int k=head[u]; k!=-1; k=e[k].next)
{
int v = e[k].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u] , low[v]);
}
else if(ins[v])
low[u] = min(low[u] , dfn[v]);
}
if(dfn[u] == low[u])
{
++bcnt;
while(1)
{
int x = stack[top--];
ins[x] = false;
belong[x] = bcnt;
if(x == u) break;
}
}
}

void SCC()
{
dcnt = bcnt = top = 0;
memset(dfn,0,sizeof(dfn));
memset(ins,false,sizeof(ins));
for(int i=1; i<=n; i++)
if(!dfn[i])
tarjan(i);
}

void SPFA(int s)
{
bool inq[N];
queue<int>q;
for(int i=0; i<=n; i++)
{
d[s][i] = INF;
inq[i] = false;
}
while(!q.empty()) q.pop();
d[s][s] = 0;
inq[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
inq[u] = false;
for(int k=head[u]; k!=-1; k=e[k].next)
{
int v = e[k].v;
int w = e[k].w;
if(belong[u] == belong[v]) w = 0;//同一个连通分量,权为0
if(d[s][u] + w < d[s][v])
{
d[s][v] = d[s][u] + w;
if(!inq[v])
{
inq[v] = true;
q.push(v);
}
}
}
}
}

int main()
{
while(scanf("%d%d",&n,&tot)!=EOF && n)
{
memset(head,-1,sizeof(head));
for(int i=0; i<tot; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,i);
}
SCC();
int K;
scanf("%d",&K);
memset(solve,false,sizeof(solve));
for(int k=0; k<K; k++)
{
int s,t;
scanf("%d%d",&s,&t);
if(!solve[s])
{
solve[s] = true;
SPFA(s);
}
if(d[s][t] == INF) printf("Nao e possivel entregar a carta\n");
else printf("%d\n",d[s][t]);
}
printf("\n");
}
return 0;
}