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