給n個點坐標,其中某些點已經相連了
求一個最小生成樹,輸出還需相連的邊的倆端點,所以得記錄一下路徑
這種輸出邊的題其實用kruskal算法應該能更簡潔一些的
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int n,vis[755],pre[755],x[755],y[755],d[755],e[755][755]; void prim() { int i,j,p,tmp; memset(vis,0,sizeof vis); for(i=2;i<=n;i++) { pre[i]=1;//記錄上一個經過的點 d[i]=e[1][i]; } d[1]=0;vis[1]=1; for(i=2;i<=n;i++) { tmp=inf;p=0; for(j=1;j<=n;j++) { if(!vis[j]&&tmp>d[j]) { tmp=d[j]; p=j; } } if(tmp!=0) printf("%d %d\n",pre[p],p); if(tmp==inf) break; vis[p]=1; for(j=1;j<=n;j++) { if(!vis[j]&&d[j]>e[p][j]) { d[j]=e[p][j]; pre[j]=p; } } } } int main() { int i,j,a,b,q; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { if(i==j) e[i][j]=0;//具體距離的值對判斷大小不影響 所以下面也可以不取根號 else e[i][j]=e[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); } } scanf("%d",&q); while(q--) { scanf("%d%d",&a,&b);//已經相連的邊直接使邊權為0 e[a][b]=e[b][a]=0; } prim(); return 0; }
“一切皆Socket!” 話雖些許
print?/* 程序頭部注釋開始(為避免提交博文中遇到的問
SUM DescriptionThere is a
//求Sn=a+aa+aaa+aaaa+aaaaa的前5項之
假設要對含有n個數的序列進行升序排列,冒泡排序算法步驟是:1
問題:int a[10];問下面哪些不可以表示a[1]的地址