为什么区间 dp 又咕咕咕了QAQ
于是随机抽取了一个幸运章节来做。
目前处于半摆烂状态。
例题1.繁忙都市
板子。写了下以前几乎没写过的堆优化 Prim。
code
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=300;
const int M=2e5+5;
int n,m;
int head[N],cnt;
struct node{
int nxt,to,w;
}e[M];
void add(int u,int v,int w){
e[++cnt].nxt=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;
}
int vis[N];
priority_queue<pii,vector<pii>,greater<pii> >q;
int Prim(int s)
{
int ans=0;
q.push(pii(0,s));
while(!q.empty())
{
int w=q.top().fi,u=q.top().se;q.pop();
if(vis[u]) continue;
ans=max(ans,w);vis[u]=1;
//cout<<w<<" "<<u<<endl;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
q.push(pii(e[i].w,v));
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
cout<<n-1<<" "<<Prim(1)<<endl;
return 0;
}
例题2.新的开始
每个点往 0 号点连一条边代表建立电站，跑最小生成树。
code
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=305;
const int M=1e5+5;
int n,m,a[N];
int head[N],cnt;
struct node{
int nxt,to,w;
}e[M];
void add(int u,int v,int w){
e[++cnt].nxt=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;
}
int vis[N],tot;
priority_queue<pii,vector<pii>,greater<pii> >q;
int Prim(int s)
{
int ans=0;
q.push(pii(0,s));
while(!q.empty())
{
int w=q.top().fi,u=q.top().se;q.pop();
if(vis[u]) continue;
ans+=w;vis[u]=1;tot++;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
q.push(pii(e[i].w,v));
}
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),add(i,0,a[i]),add(0,i,a[i]);
for(int i=1;i<=n;i++)
{
for(int j=1,w;j<=n;j++)
{
scanf("%d",&w);
if(i!=j) add(i,j,w);
}
}
cout<<Prim(0)<<endl;
//cout<<n-1<<" "<<Prim(1)<<endl;
return 0;
}
例题3.公路建设
原先就不在最小生成树上的边，加了其他边也还是不在。
只考虑最小生成树原有的边和新加进来这条就好了。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m,fa[N];
struct node{
int u,v,w;
}e[N];
int find(int x)
{
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int cnt,ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
cnt++;
scanf("%d%d%d",&e[cnt].u,&e[cnt].v,&e[cnt].w);
if(find(e[cnt].u)!=find(e[cnt].v))
{
fa[find(e[cnt].u)]=find(e[cnt].v);
ans+=e[cnt].w;
if(cnt==n-1) printf("%.1lf\n",ans/2.0);
else cout<<0<<endl;
int qwq=cnt;
while(e[qwq].w<e[qwq-1].w&&qwq>1)
{
swap(e[qwq],e[qwq-1]);
qwq--;
}
continue;
}
int qwq=cnt;
while(e[qwq].w<e[qwq-1].w&&qwq>1)
{
swap(e[qwq],e[qwq-1]);
qwq--;
}
//for(int i=1;i<=cnt;i++) cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<endl;
ans=0;int flag=0,now=cnt;cnt=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=now;i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
if(find(u)==find(v)) {flag=i;continue;}
fa[find(u)]=find(v);cnt++;
ans+=w;
}
while(flag<=cnt)
{
swap(e[flag],e[flag+1]);
flag++;
}
if(cnt==n-1) printf("%.1lf\n",ans/2.0);
else cout<<0<<endl;
}
return 0;
}