这个真的太水了——MST专辑。
如果不会MST的两种算法的同学可以出门右转了。
大致讲一下，第一题我是用Prim+堆优化的（毕竟点比较多），后面三题用的是Kruskal（习惯打，而且并查集常数实在小）
前三题是裸题，最后一题要BFS预处理图上两点间的最短距离再跑Kruskal，稍微麻烦了点
按顺序贴自己看吧（第四题数据有坑，数组要开大）
1789CODE
#include<cstdio>
#include<string>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
const int N=;
struct data
{
int x,num;
bool operator <(const data s) const
{
return s.x<x;
}
};
struct edge
{
int to,next,v;
}e[N*N];
priority_queue <data> tree;
int head[N],dis[N],n,i,j,k,ans;
string s[N];
bool vis[N];
inline int calc(int x,int y)
{
int res=;
for (int i=;i<s[x].size();++i)
if (s[x][i]!=s[y][i]) res++;
return res;
}
inline void add(int x,int y,int z)
{
e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k;
}
int main()
{
for (;;)
{
memset(e,-,sizeof(e));
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
cin>>n; k=ans=;
if (!n) break;
for (i=;i<=n;++i)
cin>>s[i];
for (i=;i<n;++i)
for (j=i+;j<=n;++j)
{
int res=calc(i,j);
add(i,j,res); add(j,i,res);
}
dis[]=;
data p;
p.x=; p.num=;
tree.push(p);
while (!tree.empty())
{
int now=tree.top().num;
tree.pop();
if (vis[now]) continue;
vis[now]=; ans+=dis[now];
for (i=head[now];i!=-;i=e[i].next)
if (e[i].v<dis[e[i].to])
{
dis[e[i].to]=e[i].v;
data p;
p.x=dis[e[i].to]; p.num=e[i].to;
tree.push(p);
} }
printf("The highest possible quality is 1/%d.\n",ans);
}
return ;
}
2485CODE
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
struct data
{
int x,y,s;
}a[N*N];
int t,n,i,j,k,x,father[N],ans;
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline void write(int x)
{
if (x/) write(x/);
putchar(x%+'');
}
inline int comp(data a,data b)
{
return a.s<b.s;
}
inline int getfather(int k)
{
return father[k]==k?k:father[k]=getfather(father[k]);
}
int main()
{
read(t);
while (t--)
{
read(n);
ans=k=;
for (i=;i<=n;++i)
for (j=;j<=n;++j)
{
read(x);
if (i==j) continue;
a[++k].x=i; a[k].y=j; a[k].s=x;
}
sort(a+,a+k+,comp);
for (i=;i<=n;++i)
father[i]=i;
for (i=;i<=k;++i)
{
int fx=getfather(a[i].x),fy=getfather(a[i].y);
if (fx!=fy)
{
ans=a[i].s;
father[fx]=fy;
}
}
write(ans); putchar('\n');
}
return ;
}
1258CODE
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
struct data
{
int x,y,s;
}a[N*N];
int n,i,j,k,x,father[N],ans;
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline void write(int x)
{
if (x/) write(x/);
putchar(x%+'');
}
inline int comp(data a,data b)
{
return a.s<b.s;
}
inline int getfather(int k)
{
return father[k]==k?k:father[k]=getfather(father[k]);
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
ans=k=;
for (i=;i<=n;++i)
for (j=;j<=n;++j)
{
read(x);
if (i==j) continue;
a[++k].x=i; a[k].y=j; a[k].s=x;
}
sort(a+,a+k+,comp);
for (i=;i<=n;++i)
father[i]=i;
for (i=;i<=k;++i)
{
int fx=getfather(a[i].x),fy=getfather(a[i].y);
if (fx!=fy)
{
ans+=a[i].s;
father[fx]=fy;
}
}
write(ans); putchar('\n');
}
return ;
}
3026CODE
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=,fx[]={,,-,},fy[]={,,,-};
struct data
{
int x,y,s;
}e[N*N];
int i,j,n,m,t,k,q[N*N*][],step[N][N],father[N*N],ans;
bool vis[N][N];
char a[N][N];
inline void BFS(int x,int y)
{
int head=,tail=;
memset(vis,,sizeof(vis));
q[][]=x; q[][]=y; vis[x][y]=; step[x][y]=;
while (head<tail)
{
int xx=q[++head][],yy=q[head][];
if (a[xx][yy]=='S'||a[xx][yy]=='A') e[++k].x=(x-)*m+y,e[k].y=(xx-)*m+yy,e[k].s=step[xx][yy];
for (int i=;i<;++i)
{
int xxx=xx+fx[i],yyy=yy+fy[i];
if (!vis[xxx][yyy]&&a[xxx][yyy]!='#'&&xxx>&&yyy>&&xxx<=n&&yyy<=m)
{
vis[xxx][yyy]=;
step[xxx][yyy]=step[xx][yy]+;
q[++tail][]=xxx; q[tail][]=yyy;
}
}
}
}
inline int comp(data a,data b)
{
return a.s<b.s;
}
inline int getfather(int k)
{
return father[k]==k?k:father[k]=getfather(father[k]);
}
int main()
{
scanf("%d\n",&t);
while (t--)
{
scanf("%d%d\n",&m,&n);
for (k=,ans=,i=;i<=n*m;++i)
father[i]=i;
for (i=;i<=n;++i)
{
for (j=;j<=m;++j)
a[i][j]=getchar();
getchar();
}
for (i=;i<=n;++i)
for (j=;j<=m;++j)
if (a[i][j]=='S'||a[i][j]=='A') BFS(i,j);
sort(e+,e+k+,comp);
for (i=;i<=k;++i)
{
int fax=getfather(e[i].x),fay=getfather(e[i].y);
if (fax!=fay)
{
ans+=e[i].s;
father[fax]=fay;
}
}
printf("%d\n",ans);
}
}