写在前面
球球啦，给我点分让我过个好年吧
期望分数： \(50 + 100 + 100 = 250pts\)
实际分数： \(0 + 100 + 100 = 200pts\)
大体浏览一遍题目，选择倒叙开题
发现最后一题是一个裸的K层图最短路，很套路的题了，前几天刚水了发K层图4倍经验，套上板子即可
第二题开始没有思路，想到一个贪心：
从大点向小点删，模拟删的过程统计答案
正确性证明：
对于任意一条边，均连着两个点，两个点迟早要删，
无论删掉那个点，答案都会加上另外一个点的权值，那不如让我们先删掉权值较大的点，来加上较小的权值
每删一个点，都要减去若干条边，每减去一条边，都不免要加另一端点的权值，
所以如果改变删点顺序，增加权值的次数是一定的，所以先删掉大的权值，尽可能不让它造成影响喽
感觉第一题不可做
发现 50% 的数据范围是 \(n \le 5\)，爆搜应该可以搞掉它
然后开始推式子找正解
设 \(d_u,e_u\) 分别为新加一个点对点权和和边权和的贡献， \(d_sum, e_sum\) 分别为前面总点权和和总边权和
假设 \(u\) 点会使答案更优，推了一手发现是这么一个式子 \(\frac{d_u}{e_u} > \frac{d_sum}{e_sum}\)
然后，嗯...就不会做了
大约一个半小时，调出T3并敲完T2的贪心（也不知道对不对）和T1的暴力，
推了半个小时式子无果后开始写考试总结（对，就是这一篇）
教练说给我们三道水题玩玩
但我太菜了/kk
依旧AK不了这场模拟赛
教练 Fake ！
T1
Description
给你n个点m条边，点有点权，边有边权。让你挑n个点，会有一个点权和，并且原图中n个点之间的边还会有一个
边权和，问你点权和与边权和的比最大是多少
数据范围：50%： \(n \le 5\)，100%：\(1 \le n,m \le 1e5\)
Solution
发现前50%的数据很水，直接爆搜即可，但是爆搜挂了
https://www.cnblogs.com/TheRoadToTheGold/p/7617433.html
可以发现一个很显然的结论：最终答案一定是两个点一条边
证明：若有多条边多个点，点的数目一定，但边的数目只会比点更多。那么不优的一个点会给更优
的一个点拖后腿，所以还不如直接选那个更优的(感性理解？)
Code
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,u,v,w;
int a[100000];
double ans;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1; i <= m; ++i){
cin >> u >> v >> w;
ans = max(ans, (a[u] + a[v]) / (w * 1.0));
}
printf("%.2lf", ans);
}
T2
Description
给你一个n个点m条边的图，让你一次删掉所有点，每删掉一个点，答案会加上所欲与该点相连的点的点权，问答案最小是多少
Solution
贪心？
事实证明，我贪的是对的
https://www.cnblogs.com/TheRoadToTheGold/p/7638794.html
Code
考场代码 & 假贪心：
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
//一个贪心的方法是：从大点向小点删
因为对于任意一条边连着两个点
两个点迟早都要删，删大的点显然比删小的点更优
不如直接从大的点开始删
模拟删点过程
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e5+5;//注意数据范围
const int INF = 1e9+7;
const int mod = 1e9+7;
struct edge{
int to, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge = 0;
struct node{
int bh, val;
bool operator < (const node &b) const { return val > b.val; }
}a[MAXN];
int n, m;
int b[MAXN];
bool vis[MAXN];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
void add_edge(int from, int to){ e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; }
int main()
{
freopen("god.in", "r", stdin);
freopen("god.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= n; ++i){
a[i].val = read(), a[i].bh = i; //记录每个点的信息
b[i] = a[i].val;//记录一下权值
}
for(int i = 1, u, v; i <= m; ++i){
u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
sort(a + 1, a + n + 1);//按权值从大到小排序
LL ans = 0;
for(int k = 1; k <= n; ++k){//依次遍历所有点
vis[a[k].bh] = true;//打上标记
// cout<<a[k].bh<<endl;
for(int i = head[a[k].bh]; i; i = e[i].nxt){
int v = e[i].to;
// cout<<v<<"lkp"<<endl;
if(!vis[v]){//有标记的证明已经删掉了
ans += b[v];//加上疲劳值
// cout<<ans<<endl;
}
}
}
cout<<ans;//输出答案
return 0;
}
T3
Description
给你一个n个点m条边的图，边有一个花费，给定一个起点和一个终点，有k次机会使经过这条边是花费为0，问花
费最小是多少
Solution
K层图最短路板子题好不好
Code
考场代码 & K层图板子：
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e6+5;
const int MAXM = 2e6+5;
const int INF = 1e18+7;
const int mod = 1e9+7;
struct edge{
int to, w, nxt;
}e[MAXM << 1];
int head[MAXN], num_edge = 0;
struct node{
int bh, val;
bool operator < (const node &b) const { return val > b.val; }
};
int n, m, k, st, ed;
int dis[MAXN];
bool vis[MAXN];
priority_queue<node> q;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
void add_edge(int from, int to, int w){ e[++num_edge] = (edge){to, w, head[from]}, head[from] =
num_edge; }
void dij(){
memset(dis, 0x3f, sizeof dis);
dis[st] = 0;
q.push((node){st, 0});
while(!q.empty()){
node u = q.top(); q.pop();
// cout<<u.bh<<endl;
if(vis[u.bh]) continue;
vis[u.bh] = true;
for(int i = head[u.bh]; i; i = e[i].nxt){
int v = e[i].to;
if(dis[v] > dis[u.bh] + e[i].w){
dis[v] = dis[u.bh] + e[i].w;
if(!vis[v]) q.push((node){v, dis[v]});
}
}
}
}
signed main()
{
freopen("move.in", "r", stdin);
freopen("move.out", "w", stdout);
n = read(), m = read(), k = read();
st = read() + 1, ed = read() + 1;
for(int i = 1, u, v, w; i <= m; ++i){
u = read() + 1, v = read() + 1, w = read();
add_edge(u, v, w), add_edge(v, u, w);
for(int j = 1; j <= k; ++j){
add_edge(u + (j - 1) * n, v + j * n, 0), add_edge(v + (j - 1) * n, u + j * n,
0);
add_edge(u + j * n, v + j * n, w), add_edge(v + j * n, u + j * n, w);
}
}
dij();
int ans = INF;
for(int i = 0; i <= k; ++i){
ans = min(ans, dis[ed + i * n]);
}
cout<<ans;
return 0;
}