班级网站的建设调查表,易加网站建设方案,google关键词分析,专业网站建设设计目录
NOIP 2017 宝藏
题目描述
输入描述:
输出描述:
输入
输出
说明
输入
输出
说明
备注:
代码实现#xff1a; NOIP 2017 宝藏
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO For…目录
NOIP 2017 宝藏
题目描述
输入描述:
输出描述:
输入
输出
说明
输入
输出
说明
备注:
代码实现 NOIP 2017 宝藏
时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld
题目描述
参与考古挖掘的小明得到了一份藏宝图藏宝图上标出了 n 个深埋在地下的宝藏屋也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是每个宝藏屋距离地面都很远也就是说从地面打通一条到某个宝藏屋的道路是很困难的而开发宝藏屋之间的道路则相对容易很多。 小明的决心感动了考古挖掘的赞助商 赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道通往哪个宝藏屋则由小明来决定。 在此基础上 小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外小明不想开发无用道路即两个已经被挖掘过的宝藏屋之间的道路无需再开发。 新开发一条道路的代价是 这条道路的长度 x 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋。 请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路使得工程总代价最小并输出这个最小值。
输入描述:
第一行两个用空格分离的正整数 n 和 m代表宝藏屋的个数和道路数。
接下来 m 行每行三个用空格分离的正整数分别是由一条道路连接的两个宝藏屋的编号编号为 1~n和这条道路的长度 v。
输出描述:
输出共一行一个正整数表示最小的总代价。
示例1
输入
复制4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 1
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
输出
复制4
4
说明 示例2
输入
复制4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 2
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
输出
复制5
5
说明 备注:
对于 20% 的数据保证输入是一棵树 1≤ n≤8 v≤ 5000 且所有的 v 都相等。
对于 40% 的数据1≤ n≤ 8 0≤ m≤ 1000 v≤ 5000 且所有的 v 都相等。
对于 70% 的数据1≤ n≤ 8 0≤ m≤ 1000 v≤ 5000。
对于 100% 的数据1≤ n≤ 12 0≤ m≤ 1000 v≤ 500000。
思路解析
看到数据点n12并且已经选择过的两个任意相邻宝藏点之间的房屋不可再开辟新的道路可以看出是状压dp。
然后这题比较妙的是因为我们并不知道当前这个点的开发线路是当前线路的第几个点可能有多种情况可以选择的开发方案我们并不知道这些方案中那些方案对于以后的抉择是最优秀的我们只能确定的是他在当前的抉择可能是最优秀的。所以我们枚举这些点的所有开发可能性有些可能性可能不存在则countinue掉但是这样枚举可能会使某些状态进行大量无效解的计算但是一定会包含最优解。又因为枚举可能性是线性的只是会让整体时间复杂度有一个常数级的倍增是可以接受的。
代码实现
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;/*** ProjectName: study3* FileName: Ex36* author:HWJ* Data: 2023/11/14 12:01*/
public class Main {static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static Input input new Input(System.in);static BufferedReader br new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) {int n input.nextInt();int m input.nextInt();int[][] map new int[n][n];int inf 1000000000;for (int i 0; i n; i) {Arrays.fill(map[i], inf);map[i][i] 0;}for (int i 0; i m; i) {int x input.nextInt() - 1;int y input.nextInt() - 1;int val input.nextInt();map[x][y] Math.min(map[x][y], val);map[y][x] Math.min(map[y][x], val);}long ans Long.MAX_VALUE;long[][] dp new long[n][1 n]; // dp[i][st]表示当前状态st在第i层的最小花费数。for (int i 0; i n; i) {Arrays.fill(dp[i], inf);}for (int i 0; i n; i) {dp[0][1 i] 0;}for (int i 1; i 1 n; i) {for (int j (i - 1) i; j 0; j (j - 1) i) {int point j ^ i;long sum 0;for (int x 0; x n; x) {int min inf;if (((1 x) point) 0) continue;for (int y 0; y n; y) {if (((1 y) j) 0) continue;min Math.min(min, map[x][y]);}summin;}if (sum inf) continue;for (int k 1; k n; k) {dp[k][i] Math.min(dp[k][i], dp[k - 1][j] k * sum);}}}for (int i 0; i n; i) {ans Math.min(ans, dp[i][(1 n) - 1]);}System.out.println(ans);}static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader new BufferedReader(new InputStreamReader(stream), 32768);tokenizer null;}public String next() {while (tokenizer null || !tokenizer.hasMoreTokens()) {try {tokenizer new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str null;try {str reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}
