CSP-S2游记
10.31
这一天啥也没干，就中午AC了一道绿题加晚上AC一道绿题，然后都在看洛谷的帖子。
11.1
早上6:50就来学校自习，顺便又AC一道绿题。接着又是在逛洛谷。到了10:00就准时回家了。 回家之后刷视频刷到11:50，吃顿难吃的午饭就准备去考场了。
跟着学校的车来到考场后也是遇到了朋友，跟他聊了一会儿天，然后发现跟我一起来的同学没带准考证，于是我就先进考场了。
T1
考试的时候我一直以为T1是道橙题，刚开始我一直在想贪心，好不容易把代码写出来了，发现小样例都过不了，这时候坐我旁边的初中生和小学生把键盘敲得超级响快把我紧张死了，连题目都读不下去了。心态崩了，随便写个dfs了事先拿20分再说。
考试最后10分钟发现一个特殊性质A随便加了几行代码再骗5分。
得分: 25分
T2
刚开始看题目，一看是最小生成树瞬间觉得自己有救了，没看清题目就开始打代码。结果打出一坨大的。等彻底理解题意时已经过了40分钟了。
后来也是成功打出代码并且过了前三个样例。最后一个样例调了我2个小时。
思路： kurskal，用小根堆给每条边排序，把乡镇连接的城市i，j看成一条i，j的路，边权为a_ik+c_k+a_kj。并且标记需要乡镇k这个中转站，加入堆中。跑kurskal时如果遇到需要中转站的边那就把乡镇城市化，并且把所有连边减去c_k当正常边加入到堆中。
代码：
#include<bits/stdc++.h>
using namespace std;
int father[10005],n,m,k,c[15];
long long ans;
vector<long long>s[15];
struct edge{
int u,v;
long long w;
int p;
bool operator<(const edge &it)const{
return w>it.w;
}
};
priority_queue<edge> q;
int find(int x){
if(x==father[x])return x;
return father[x]=find(father[x]);
}
void unionn(int x,int y){
father[find(y)]=find(x);
return;
}
void kruskal(){
int kk=0;
while(!q.empty()){
int u=q.top().u;
int v=q.top().v;
long long w=q.top().w;
int p=q.top().p;
q.pop();
if(find(u)!=find(v)){
if(p>0){
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)q.push({i,j,s[p][i-1]+s[p][j-1],0});
}
ans+=w;
unionn(u,v);
kk++;
}
if(kk==n-1)break;
}
return;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++){
int u,v;
long long w;
scanf("%d %d %lld",&u,&v,&w);
q.push({u,v,w,0});
}
for(int i=1;i<=k;i++){
cin>>c[i];
for(int j=1;j<=n;j++){
long long w;
scanf("%lld",&w);
s[i].push_back(w);
}
for(int j=1;j<n;j++)
for(int k=j+1;k<=n;k++)
if(j!=k){
if(c[i]==0) q.push({j,k,s[i][j-1]+s[i][k-1],0});
else q.push({j,k,s[i][j-1]+c[i]+s[i][k-1],i});
}
}
kruskal();
cout<<ans;
return 0;
}
得分： [ 44 , 64 ]
T3&T4
忘记做了，没时间做。
总分： [61,89] 坐标 FJ
总结
太难了，最后我不小心把考场的草稿纸带出来了 会不会因此保龄。