暑期集训模拟赛3

今天除了改成\(0\)分的\(T4\)一切安好……

NO.1 中中救援队

原型：安慰奶牛

题目描述

中中酷爱滑雪，某日突发奇想，带领所有\(BDEZ\)的\(OIER\)去\(Alps\)滑雪，不幸的是，中中和\(OIER\)们遭遇了雪崩，除了中中，所有的\(OIER\)们都埋在了雪坑里，此时，中中救援队闪亮登场~！（中中救援队只有中中一个人！\(Orz\)！）

雪崩之后，出现了\(N\)个雪坑，每个雪坑都有一名\(OIER\)深陷其中，只有中中幸免，现在中中找到了M条双向道路，每条道路都会连接两个雪坑，但是，由于中中是路痴（-_-||），所以中中希望去除\(M\)条道路中尽可能多的道路，但是还要保证任一雪坑都能到达其他的雪坑，所以要先选择留下\(N-1\)条道路，中中可以从任意一个雪坑出发，并且任务完成后要回到出发点（起点的雪坑和终点的雪坑也需要消耗体力），而且中中只记得他选择的道路 中中每到一个雪坑\(i\)，都会消耗一定的体力值\(t_i\)，即使这个雪坑的\(OIER\)已被救出。第\(j\)条道路连接\(x,y\)两个雪坑，而从\(x\)到达\(y\)也需要消耗体力值\(energy\) 由于时间紧迫，中中请你这名\(OIER\)帮助他计算下救出这\(N\)名\(OIER\)所消耗的最小体力值是多少

输入格式

输入第一行两个整数\(N\)和\(M\)，表示有\(N\)名\(OIER\)，\(M\)条连接的道路

接下来\(N\)行，每行一个整数\(t_i\)，表示第\(i\)个雪坑需要消耗中中的体力值

然后\(M\)行，每行三个整数\(x,y,energy\)，表示从\(x\)坑滑到\(y\)坑需要消耗的体力值为\(energy\)

输出格式

第\(1\)行，一个整数，为中中消耗的最小体力值

样例 样例输入

5 7
6
5
13
8
18
4 1 7
5 2 5
1 5 16
2 3 20
3 1 18
4 3 12
2 4 15

样例输出

154

数据范围与提示

对于\(30\%\)的数据 \(5\le N\le 100，N-1\le M\le 500 1\le t_i\le 100 x\le N，y\le N，1\le energy\le 100\)

对于全部数据 \(5\le N\le 10000，N-1\le M\le 100000 1\le t_i\le 1000 x\le N，y\le N，1\le energy\le 1000\)

结果保证不超过\(2^{31}-1\)

分析

看到题目中只保留\(N-1\)条边，且要求消耗能量最小即路径长最小，那么就是一个最小生成树板子题了，但是处理边权需要考虑一下。
因为每条路径一定要经过两遍，所以首先需要让路径长乘以\(2\)，又因为每个点的点权也需要计算，所以我们还需要加上路径两端的点权，然后跑最小生成树就行了。
因为起点和终点也要计算，而除了终点都是经过两次，又因为处理的时候没有把每个起点和重点的值计算两边，所以需要找出最小的点权，并且从那里作为起点，最后就是最小生成树的值加上这个最小的点权。

代码 #include<bits/stdc++.h> using namespace std; const int maxn = 1e4+10; struct Node{ int x,y,val; }e[maxn*10]; int n,m; int mn=0x7f7f7f7f; int t[maxn],fa[maxn]; bool cmp(Node a,Node b){ return a.val<b.val; } int Find(int x){//并查集 return x==fa[x]?x:(fa[x]=Find(fa[x])); } int kruscal(){//最小生成树板子…… int ans = 0; sort(e,e+m,cmp); for(int i=0;i<m;++i){ int x = Find(e[i].x); int y = Find(e[i].y); if(x != y){ fa[x] = y; ans += e[i].val; } } return ans; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;++i)fa[i]=i; for(int i=0;i<n;++i){ scanf("%d",&t[i]); } for(int i=0;i<m;++i){ scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].val); e[i].val = 2*e[i].val+t[e[i].x-1]+t[e[i].y-1];//处理边权 } for(int i=0;i<n;++i){//找到最小点权 if(mn>t[i])mn=t[i]; } int ans = mn+kruscal();//计算答案 printf("%d\n",ans); return 0; } NO.2 家务活 题目描述

农场主约翰家人有\(N (3\le N\le 10,000)\)件家务活需要完成，完成第\(i\)件家务活需要\(T_i(1\le T_i\le 100)\)的时间，在做第\(i\)件家务活之前约翰必须完成若干个家务活，我们称这些家务为\(i\)的必备家务。至少有一个家务没有必备家务，第一件家务没有必备家务。

约翰已经安排好完成家务活的顺序，家务活\(k\)的必备家务活只会出现在区间\([1,k-1]\)之间。没有依赖关系的家务活可以同时进行。

现在请你计算约翰家人完成所有家务的最短时间。

输入格式

第一行为一个整数\(N\)，表示有\(N\)件家务活。