Living-Dream 系列笔记强势回归（雾）
T1
并查集妙妙题。
很容易想到一种朴素的贪心策略：
对于所以物品按照价格从大到小排序，
然后每一个物品，找到最晚的没有卖物品的那一天卖掉此物品。
这样贪心的时间复杂度为 \(O(\max d_i \times n)\)，可以通过。
考虑如何优化此贪心。
可以发现朴素贪心时间复杂度的瓶颈
在于找到最晚的没有卖物品的那一天，
于是我们采用并查集，
每次卖出物品时将当前这一天与上一天合并，
然后每次在第 \(x\) 天查询 \(fa_x\) 即为所求。
时间复杂度是 \(O(n \log \max d_i)\) 的。
#include<bits/stdc++.h>
using namespace std;
int n,ans,maxi;
pair<int,int> a[10031];
bool vis[10031];
int fa[10031];
bool cmp(pair<int,int> a,pair<int,int> b){
return a.first>b.first;
}
int fnd(int x){
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
int main(){
while(cin>>n){
ans=0,maxi=-1e9;
for(int i=1;i<=n;i++)
cin>>a[i].first>>a[i].second,maxi=max(maxi,a[i].second);
sort(a+1,a+n+1,cmp);
memset(vis,0,sizeof(vis));
for(int i=1;i<=maxi;i++) fa[i]=i;
for(int i=1;i<=n;i++){
int pos=fnd(a[i].second);
if(pos>0)
ans+=a[i].first,fa[pos]=pos-1;
}
cout<<ans<<'\n';
}
return 0;
}
似乎还有一种堆做法，有心情再更。
upd：堆做法在本人的算法竞赛进阶指南笔记中有。
T2
最小生成树的板子。
最小生成树的定义：\(n\) 点 \(m\) 边的无向连通图中边权和最小的 \(n\) 点树。
如何求最小生成树：
-
\(\texttt{Kruskal}\)
-
\(\texttt{Prim}\)（暂未学习）
\(\texttt{Kruskal}\) 算法：
将 \(m\) 边按照边权从小到大排序，
然后对于两个节点，
若它们未联通（用并查集维护），
就对它们进行连边即可。
证明：（询问）。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[200031];
struct E{
int u,v,w;
}e[200031];
bool cmp(E x,E y){
return x.w<y.w;
}
int fnd(int x){
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void mrg(int x,int y){
x=fnd(x),y=fnd(y);
fa[x]=y;
}
int kruskal(){
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
if(fnd(e[i].u)!=fnd(e[i].v)){
mrg(e[i].u,e[i].v);
ans+=e[i].w;
cnt++;
if(cnt==n-1) return ans;
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp);
int Ans=kruskal();
if(Ans==-1) cout<<"orz";
else cout<<Ans;
return 0;
}
T3
大水题。
将答案累加改为答案取 \(\max\) 即可。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[100031];
struct E{
int u,v,w;
}e[100031];
bool cmp(E x,E y){
return x.w<y.w;
}
int fnd(int x){
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void mrg(int x,int y){
x=fnd(x),y=fnd(y);
fa[x]=y;
}
int kruskal(){
int ans=-1e9,cnt=0;
for(int i=1;i<=m;i++){
if(fnd(e[i].u)!=fnd(e[i].v)){
mrg(e[i].u,e[i].v);
ans=max(ans,e[i].w);
cnt++;
if(cnt==n-1) return ans;
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp);
//if(Ans==-1) cout<<"orz";
cout<<kruskal();
return 0;
}
T4
大水题 \(\times \ 2\)。
终止条件改为连通块数量为 \(k\) 即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int fa[200031];
struct E{
int u,v,w;
}e[200031];
bool cmp(E x,E y){
return x.w<y.w;
}
int fnd(int x){
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void mrg(int x,int y){
x=fnd(x),y=fnd(y);
fa[x]=y;
}
bool check(){
int cnt=0;
for(int i=1;i<=n;i++)
if(fa[i]==i) cnt++;
return cnt==k;
}
int kruskal(){
int ans=0;
for(int i=1;i<=m;i++){
if(fnd(e[i].u)!=fnd(e[i].v)){
mrg(e[i].u,e[i].v);
ans+=e[i].w;
if(check()) return ans;
}
}
return -1;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp);
int Ans=kruskal();
if(Ans==-1) cout<<"No Answer";
else cout<<Ans;
return 0;
}
习题 T1
大水题 \(\times \ 3\)。
将边权改为距离，端点改为下标，
终止条件改为 \(cnt=(s-1)-(p-1)=s-p\) 即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,tot;
map<int,int> fa;
int x[531],y[531];
struct E{
int u,v;
double w;
}e[250031];
bool cmp(E x,E y){
return x.w<y.w;
}
double get_dis(int x,int y,int xx,int yy){
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
int c(int x){
int y=0;
while(x) y++,x/=10;
return y;
}
int fnd(int x){
return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
void mrg(int x,int y){
x=fnd(x),y=fnd(y);
fa[x]=y;
}
double kruskal(){
double ans=0;
int cnt=0;
for(int i=1;i<=tot;i++){
if(fnd(e[i].u)!=fnd(e[i].v)){
mrg(e[i].u,e[i].v);
ans=e[i].w;
cnt++;
if(cnt==n-m) return ans;
}
}
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
e[++tot].w=get_dis(x[i],y[i],x[j],y[j]),
e[tot].u=i,
e[tot].v=j;
sort(e+1,e+tot+1,cmp);
double Ans=kruskal();
cout<<setprecision(2)<<fixed<<Ans;
return 0;
}