UESTC 1220 The Battle of Guandu(最短路)

题目大意

背景:曹操和袁绍在官渡决战。
现有 $N$ 个村庄, $M$ 个战场。对于村庄 $i$ ,曹操可以挑选一些人去给定的 $x_i$ 战场充军(曹操军队),每挑选一个人需要花费 $c_i$ 元。由于村子的人惧怕袁绍的报复,所以村庄会送相同数量的人去给定的 $y_i$ 战场充军(袁绍军队)。
每个战场都有一个重要性 $w_i$。为了保证曹操的胜利,重要性为 $2$ 的战场曹操军队士兵数量要严格多于袁绍,重要性为 $1$ 的战场曹操军队士兵数量不能少于袁绍,重要性为 $0$ 的战场则无所谓。一开始双方都没有军队,问为保证胜利,曹操需要花费的最小费用。无解输出 $-1$。
$(1 \leq N, M \leq 10^5,1 \leq x_i, y_i \leq 10^5,0 \leq c_i \leq 10^5,w_i \in {0, 1, 2})$ 时限 $3s$。

解题思路

最短路

一个巧妙的想法是只考虑己方军队(曹操)。那么每次挑选相当于从 $y_i$ 战场向 $x_i$ 战场送兵。由于 $0$ 战场(重要性为 $0$) 不用考虑胜负,所以军队士兵的最终来源一定是 $0$ 战场, $1$ 战场只能作为中间点过度。由此进行建图:

  • 源点 $s$ 向所有 $0$ 战场连一条费用为 $0$ 的有向边
  • $y_i$ 战场向 $x_i$ 战场连一条费用为 $c_i$ 的有向边

直接跑单源最短路,然后将所有 $2$ 战场的权值加起来便是答案了。(若有一个不能到达则输出 $-1$)。

Ps: 是道好题,6rz出题人。

解题代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

struct Edge {
int to, cost, next;
Edge( int to = 0, int cost = 0, int next = 0 ) : to(to), cost(cost), next(next) {}
} G[MAXN << 1];
int n, m;
int tot, head[MAXN];
int x[MAXN], y[MAXN], c[MAXN], w[MAXN];
bool inque[MAXN];
ll d[MAXN];

void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
void readData(int* v, int num)
{

for( int i = 0; i < num; ++ i ) scanf("%d", v + i);
}
void readAll()
{

readData(x, n);
readData(y, n);
readData(c, n);
readData(w, m);
}
void addEdge(int u, int v, int cost)
{

G[tot] = Edge(v, cost, head[u]);
head[u] = tot++;
}
void mapping()
{

for( int i = 0; i < m; ++ i ) {
if( !w[i] ) addEdge(0, i + 1, 0);
}
for( int i = 0; i < n; ++ i ) {
addEdge(y[i], x[i], c[i]);
}
}
ll spfa(int s)
{

memset(d, -1, sizeof(d));
queue<int> que;
d[s] = 0;
inque[s] = true;
que.push(s);

while( !que.empty() ) {
int u = que.front(); que.pop();
inque[u] = false;
for( int i = head[u]; ~i; i = G[i].next ) {
Edge& e = G[i];
if( d[e.to] == -1 || d[e.to] > d[u] + e.cost ) {
d[e.to] = d[u] + e.cost;
if( !inque[e.to] ) que.push(e.to);
inque[e.to] = true;
}
}
}
ll ans = 0;
for( int i = 0; i < m; ++ i ) {
if( w[i] == 2 ) {
if( d[i + 1] == -1 ) {
ans = -1;
break;
}
ans += d[i + 1];
}
}
return ans;
}
int main()
{

int T, cas = 0;
scanf("%d", &T);
while( T-- ) {
init();
scanf("%d %d", &n, &m);
readAll();
mapping();
ll ans = spfa(0);
printf("Case #%d: ", ++cas);
if( ~ans ) printf("%lld\n", ans);
else puts("-1");
}

return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!