SDNU 1030.烽火台

1030.烽火台

Time Limit: 1000 MS Memory Limit: 32768 KB
Total Submission(s): 37 Accepted Submission(s): 6

Description
烽火台是一种传递信息的手段,通过在烽火台处燃起狼烟,使其他烽火台或要传递到的人看到,从而达到传递信息的目的。

已知有N个烽火台围绕一座城池,每个烽火台k燃起狼烟都需要一定的时间,记为该烽火台燃起狼烟所需的代价Wk,两座能够传递信息的烽火台i、j之间,因为距离等原因也需要一定的时间,记为传递信息的单位代价Vij。
所有烽火台及若干传递信息的路径可以组成一棵树的结构。其中,树根为城池。每个烽火台为一个节点,若两座烽火台之间能够传递信息,则两烽火台之间存在一条边。对于每条边来说,传递信息的代价为 该边所连接的子树中所有点代价的和 × 该边的单位代价。
根据输入数据,构建一棵树,使得所有边的总代价最小。

Input
多组测试数据。
第一行两个整数N、M(0 <= N,M <= 1000),为节点的数量及所有可能的边的数量。
第二行N个整数,第k个整数代表第k个节点的代价Wk(1 <= Wk <= 2^10)。
之后M行,每行3个整数i、j、v,代表第i个节点能够传递信息给第j个节点,传递信息的代价为v(1 <= v <= 2^10)。
其中,城池为第1个节点。

Output
最小的总代价。
若有节点无法连接到根,则输出:No Answer

Sample Input
7 7
200 10 20 30 40 50 60
1 2 1
2 3 3
2 4 2
3 5 4
3 7 2
3 6 3
1 5 9

Sample Output
1210

题解:
oj第一页上的题,我做的时候只有5个人a了,还以为很难(确实很难,不过是读题比较困难)。其实是一道最短路的模板题。
先解释一下题意把,1 是起点,要把 1 和别的所有的点都连起来,求出最小的花费。每条边的花费 = 该边所连接的子树中所有点代价的和 × 该边的单位代价。听着很玄学,我们结合样例分析一下。
Alt text
如图,除了去 5 的路径有两条,其他的都是唯一的,不难得出最后的路径走了单位花费为 4 的路。
那么样例就是:(10+20+30+40+50+60) X 1 + 30 × 2 + (20+40+50+60) × 3 + 40 × 4 + 50 × 3 + 60 × 2 = 1210。
一开始看懂样例的时候我还以为是最小生成树,仔细一想不对,在看一下上面这个式子,可以变化一下:
10 X 1 + 20 X (1 + 3) + 30 X (1 + 2) + 40 X (1 + 3 + 4) + 50 X (1 + 3 + 3) + 60 X (1 + 2 + 3) = 1210。
没错,不难发现,原来说的这么花里胡哨,就是从 1 到 i 点的最短路 X 该点的花费,那么一切就迎刃而解了。

Ac代码:

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

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

struct Edge
{
int v;
int cost;
Edge(int _v = 0,int _cost = 0):v(_v),cost(_cost){}
};

vector<Edge> E[MAXN];

void addEdge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}

long long dist[MAXN];
bool vis[MAXN];
int cnt[MAXN],w[MAXN];
int n,m;

bool SPFA()
{
memset(vis,0,sizeof vis);
for(int i = 0; i <= n; i++)
dist[i] = LLONG_MAX;

vis[1] = true;
dist[1] = 0;
queue<int> q;

while(!q.empty())
{
q.pop();
}
q.push(1);
memset(cnt,0,sizeof cnt);
cnt[1] = 1;

while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;

for(int i = 0; i < E[u].size(); i++)
{
int v = E[u][i].v;
if(dist[v] > dist[u] + E[u][i].cost)
{
dist[v] = dist[u] + E[u][i].cost;
if(!vis[v])
{
vis[v] = 1;
q.push(v);
if(++cnt[v] > n)
{
return 0;
}
}
}
}
}

return 1;
}

int main()
{
while(cin >> n >> m)
{
int a,b,c;
for(int i = 1; i <= n; i++)
{
cin >> w[i];
}
for(int i = 0; i < m; i++)
{
cin >> a >> b >> c;
addEdge(a,b,c);
addEdge(b,a,c);
}
int flag;
flag = SPFA();
long long sum = 0;
for(int i = 2; i <= n; i++)
{
if(dist[i] == LLONG_MAX)
{
flag = 0;
break;
}
sum += w[i] * dist[i];
}
if(flag)
cout << sum << '\n';
else
cout << "No Answer" << '\n';
for(int i = 1; i <= n; i++)
E[i].clear();

}
return 0;
}
我好饿呀!求打赏!