1.模板代码
#include <iostream> #include <cstring> using namespace std; const int SIZE=101; const int INF=0x7fffffff; int a[SIZE][SIZE]; int n, m; void init() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=INF; } void prim(int u0) { int lowcost[SIZE], nearV[SIZE]; int sum=0; for(int i=1;i<=n;i++) {lowcost[i]=a[u0][i]; nearV[i]=u0;} nearV[u0]=-1; lowcost[u0]=0; for(int i=1;i<n;i++) { int minV=INF, v=-1; for(int j=1;j<=n;j++) { if(nearV[j]!=-1 && lowcost[j]<minV) { minV=lowcost[j]; v=j; } } cout<<nearV[v]<<" "<<v<<" "<<minV<<endl; nearV[v]=-1; sum+=minV; for(int j=1;j<=n;j++) { if(nearV[j]!=-1 && lowcost[j]>a[v][j]) { lowcost[j]=a[v][j]; nearV[j]=v; } } } cout<<"MST:"<<sum<<endl; } int main() { int u,v,w; while(cin>>n>>m) { init(); for(int i=0;i<m;i++){cin>>u>>v>>w; a[u][v]=a[v][u]=w;} cout<<"\n\n"; prim(1); } return 0; }
2.POJ 2349
题意:有P个点,用坐标给出,有两种联系方式:1每个点可以和距离在D以内的点相互联系,2有S个专门的卫星通道,两个点直接联系;
求D最小多少可以把这个图连起来
题解:首先不考虑S个卫星通道,先求最小生成树,用卫星通道把最小生成树中最大的S-1个边代替掉,然后剩下的最大的那条边的值就是能把整个图连起来的D的最小值.
#include <iostream> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; const int SIZE=505; int S, P; int x[SIZE], y[SIZE], cnt; double w[SIZE][SIZE], pur[SIZE]; void init() { for(int i=0;i<P;i++) w[i][i]=0x7fffffff; for(int i=0;i<P;i++) for(int j=i+1;j<P;j++) { double dd; dd=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); w[i][j]=w[j][i]=dd; } } void prim(int u0) { int nearV[SIZE]; double lowcost[SIZE]; cnt=0; for(int i=0;i<P;i++) { nearV[i]=u0; lowcost[i]=w[u0][i]; } nearV[u0]=-1; for(int i=1;i<P;i++) { double minV=0x7fffffff; int u=-1; for(int j=0;j<P;j++) { if(nearV[j]!=-1 && minV>lowcost[j]) { minV=lowcost[j]; u=j; } } if(u==-1) {cout<<-1<<endl; return;} nearV[u]=-1; pur[cnt++]=minV; for(int i=0;i<P;i++) { if(nearV[i]!=-1 && lowcost[i]>w[u][i]) { lowcost[i]=w[u][i]; nearV[i]=u; } } } sort(pur,pur+cnt); printf("%.2f\n",pur[cnt-S]); } int main() { int T; cin>>T; while(T--) { cin>>S>>P; for(int i=0;i<P;i++) cin>>x[i]>>y[i]; init(); prim(0); } return 0; }