1月3日星期六9:00-12:00
P1807 最长路
题目描述
设 G 为有 n 个顶点的带权有向无环图，G 中各顶点的编号为 1 到 n，请设计算法，计算图 G 中 1, n 间的最长路径。
输入格式
输入的第一行有两个整数，分别代表图的点数 n 和边数 m。
第 2 到第 (m + 1) 行，每行 3 个整数 u, v, w（u<v），代表存在一条从 u 到 v 边权为 w 的边。
输出格式
输出一行一个整数，代表 1 到 n 的最长路。
若 1 无法到达 n，请输出 -1。
输入输出样例 #1
输入 #1
2 1
1 2 1
输出 #1
1
说明/提示
【数据规模与约定】
- 对于
20\%的数据，n \leq 100，m \leq 10^3。 - 对于
40\%的数据，n \leq 10^3，m \leq 10^{4}。 - 对于
100\%的数据，1 \leq n \leq 1500，0 \leq m \leq 5 \times 10^4，1 \leq u, v \leq n，-10^5 \leq w \leq 10^5。
代码
// P1807最长路
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int d[2100];
int f[2100];
int pre[2100];
struct Edge {
int from, to, next, len;
} a[51000];
void add(int u, int v, int len) {
a[++k].from = u;
a[k].to = v;
a[k].len = len;
a[k].next = pre[u];
pre[u] = k;
}
queue<int> q;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, len;
cin >> u >> v >> len;
add(u, v, len);
}
// spfa算法求最长路
memset(d, 0xc0, sizeof(d));
d[1] = 0;
q.push(1);
f[1] = true;
while (!q.empty()) {
int head = q.front();
f[head] = false;
for (int i = pre[head]; i != 0; i = a[i].next) {
int to = a[i].to;
if (d[to] < d[head] + a[i].len) {
d[to] = d[head] + a[i].len;
if (!f[to]) {
q.push(to);
f[to] = true;
}
}
}
q.pop();
}
if (d[n] != 0xc0c0c0c0) {
cout << d[n];
} else {
cout << -1;
}
return 0;
}
P1576 S+03Z03最小的手续费
描述
某商业银行规定，两个银行账户之间转账，银行需要收取一定的手续费，且不同的账户之间转账，手续费可能不同。
现给定n个账户中的某些账户之间互相转账的手续费（转账后另一个账户收到的费用 = 转账费用 - 手续费），请问A如果希望通过转账使得B收到100元，那么A需要准备多少钱？
输入描述
第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。(0<n<=2000)
以下m行每行输入三个正整数x,y,z，表示编号为x的人和编号为y的人之间互相转账需要扣除z%的手续费 (z<100)。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账
输出描述
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
用例输入 1
3 3
1 2 1
2 3 2
1 3 3
1 3
用例输出 1
103.07153164
代码
//注意有向还是无向图
//d数组应该是double
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t, k;
struct Edge {
int from, to, next;
double len;
} a[201000];
int pre[2100];
void add(int u, int v, double len) {
a[++k].from = u;
a[k].to = v;
a[k].len = len;
a[k].next = pre[u];
pre[u] = k;
}
double d[2100];
int f[2100];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, len;
cin >> u >> v >> len;
add(u, v, (double)(100 - len) / 100);
add(v, u, (double)(100 - len) / 100);
}
cin >> s >> t;
memset(d, 0, sizeof(d));
d[s] = 1;
for (int i = 1; i <= n; i++) {
int mi = -1;
for (int j = 1; j <= n; j++) {
if (!f[j] && (mi == -1 || d[j] > d[mi])) {
mi = j;
}
}
f[mi] = true;
for (int j = pre[mi]; j != 0; j = a[j].next) {
int to = a[j].to;
if (d[to] < d[mi] * a[j].len) {
d[to] = d[mi] * a[j].len;
}
}
}
printf("%.8f", 100 / d[t]);
return 0;
}
//spfa:注意事项:d数组是double 无向图边数最大值应该是m*2;
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t, k;
struct Edge {
int from, to, next;
double len;
} a[210000];
int pre[2100];
void add(int u, int v, double len) {
a[++k].from = u;
a[k].to = v;
a[k].len = len;
a[k].next = pre[u];
pre[u] = k;
}
double d[2100];
int f[2100];
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, len;
cin >> u >> v >> len;
add(u, v, (double)(100 - len) / 100);
add(v, u, (double)(100 - len) / 100);
}
cin >> s >> t;
memset(d, 0, sizeof(d));
d[s] = 1;
queue<int> q;
q.push(s);
f[s] = true;
while (!q.empty()) {
int head = q.front();
q.pop();
f[head] = false;
for (int i = pre[head]; i != 0; i = a[i].next) {
int to = a[i].to;
if (d[to] < d[head] * a[i].len) {
d[to] = d[head] * a[i].len;
if (!f[to]) {
q.push(to);
f[to] = true;
}
}
}
}
printf("%.8f", 100 / d[t]);
return 0;
}
P1529 [USACO2.4] 回家 Bessie Come Home
题目描述
现在是晚餐时间，而母牛们在外面分散的牧场中。
Farmer John 按响了电铃，所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓（在给出的测试数据中，总会有且只有一只最快的母牛）。在挤奶的时候（晚餐前），每只母牛都在她自己的牧场上，一些牧场上可能没有母牛。
每个牧场由一条条道路和一个或多个牧场连接（可能包括自己）。有时，两个牧场（可能是字母相同的）之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此，所有的母牛最后都能到达谷仓，并且母牛总是走最短的路径。当然，母牛能向着任意一方向前进，并且她们以相同的速度前进。牧场被标记为 \texttt{a} \ldots \texttt{z} 和 \texttt{A} \ldots \texttt{Y}，在用大写字母表示的牧场中有一只母牛，小写字母中则没有。 谷仓的标记是 \texttt{Z}，注意没有母牛在谷仓中。
注意 \texttt{m} 和 \texttt{M} 不是同一个牧场。
输入格式
第一行一个整数 P（1\leq P \leq 10^4），表示连接牧场（谷仓）的道路的数目。
接下来 P 行，每行用空格分开的两个字母和一个正整数：被道路连接牧场的标号和道路的长度（道路长度均不超过 10^3）。
输出格式
单独的一行包含二个项目：最先到达谷仓的母牛所在的牧场的标号，和这只母牛走过的路径的长度。
输入输出样例 #1
输入 #1
5
A d 6
B d 3
C e 9
d Z 8
e Z 3
输出 #1
B 11
说明/提示
翻译来自 NOCOW
USACO 2.4
代码
// P1529 [USACO2.4] 回家 Bessie Come Home
// 注意有向无向
#include <bits/stdc++.h>
using namespace std;
int n, k;
struct Edge {
char from, to;
int next, len;
} a[21000];
int pre[128];
void add(char u, char v, int len) {
a[++k].from = u;
a[k].to = v;
a[k].len = len;
a[k].next = pre[u];
pre[u] = k;
}
int d[128];
bool f[128];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
char u, v;
int len;
cin >> u >> v >> len;
add(u, v, len);
add(v, u, len);
}
queue<char> q;
memset(d, 0x3f, sizeof(d));
d['Z'] = 0;
q.push('Z');
f['Z'] = true;
while (!q.empty()) {
char head = q.front();
q.pop();
f[head] = false;
for (int i = pre[head]; i != 0; i = a[i].next) {
char to = a[i].to;
if (d[to] > d[head] + a[i].len) {
d[to] = d[head] + a[i].len;
if (!f[to]) {
q.push(to);
f[to] = true;
}
}
}
}
int mi = INT_MAX;
char num;
for (int i = 65; i < 90; i++) {
if (mi > d[i]) {
mi = d[i];
num = i;
}
}
cout << num << " " << mi;
return 0;
}