2018-3-24

簡單的最小生成樹問題。

題目大意是：
給你n個字符串，他們的distance就是串中不同字符的個數，要求算出所有串的distance’s 最小 sum ；

#include<iostream> #include<cstring> #define MAX 10 using namespace std;const int N = 2000, M = 7; char x[N+1][M+1]; int dis[N+1][N+1],D[N+1]; bool z[N+1]; int n;int getDis(int i,int j){int s=0;for (int k=0;x[i][k]!='\0';k++){if (x[i][k]!=x[j][k]) s++;}return s; }int prim(){int i,j,s=0;for (j=0;j<n;j++){D[j]=dis[0][j];}z[0]=1;int min_path,min_point;for (i=1;i<n;i++){min_path=MAX;for (j=0;j<n;j++){if (z[j]) continue;if (D[j]<min_path){min_path=D[j];min_point=j;}}D[min_point]=MAX;z[min_point]=1;s+=min_path;for (j=0;j<n;j++){if (z[j]) continue;if (dis[min_point][j]<D[j]){D[j]=dis[min_point][j];}}}return s; }int main(){int i,j;while (cin>>n&&n){for (i=0;i<n;i++){cin>>x[i];}for (i=0;i<n;i++){for (j=0;j<n;j++){dis[i][j]=MAX;}} int d;memset(z,false,sizeof(z));for (i=0;i<n-1;i++){for (j=i+1;j<n;j++){d=getDis(i,j);dis[i][j]=d;dis[j][i]=d;}}cout<<"The highest possible quality is 1/"<<prim()<<"."<<endl;}return 0; }

直接使用prim算法求解即可，需要注意的是，輸出的最后有一個小點。

或者你也可以用kruskal算法

#include<iostream> #include<cstring> #include<algorithm> #define MAX 10 using namespace std;const int N = 2000, M = 7; char x[N+1][M+1]; int f[N+1]; int n,k;struct xd{int s,e,v; }dis[N*N/2];bool cmp(struct xd a,struct xd b){return a.v<b.v; }int getDis(int i,int j){int s=0;for (int k=0;x[i][k]!='\0';k++){if (x[i][k]!=x[j][k]) s++;}return s; }int find(int p){int q=p;while (p!=f[p]){p=find(f[p]);}while (q!=p){f[q]=p;q=f[q];}return p; }int kruskal(){int i,s=0;for (i=0;i<n;i++){f[i]=i;}for (i=0;i<k;i++){int ii=find(dis[i].s),jj=find(dis[i].e);if (ii!=jj){f[ii]=jj;s+=dis[i].v;}}return s; }int main(){int i,j,d;while (cin>>n&&n){for (i=0;i<n;i++){cin>>x[i];}k=0;for (i=0;i<n-1;i++){for (j=i+1;j<n;j++){d=getDis(i,j);dis[k].s=i;dis[k].e=j;dis[k].v=d;k++;}}sort(dis,dis+k,cmp);cout<<"The highest possible quality is 1/"<<kruskal()<<"."<<endl;}return 0; }

注意并查集路徑的壓縮。

——————————————————————————————————————————————————-

2018-5-22

prime算法求解：

#include<iostream> #include<cstdio> #include<cstring> #define inf 0x3f3f3f3f using namespace std;const int N = 2000, M = 7; char x[N+1][M+1]; int d[N+1][N+1]; int dis[N+1]; bool f[N+1]; int n,res;int cal(int i,int j){int cnt=0;for (int k=0;k<M;k++){if (x[i][k]!=x[j][k]){cnt++;}}return cnt; }void init(){for (int i=0;i<n;i++){for (int j=0;j<n;j++){int tmp=cal(i,j);d[i][j]=tmp;d[j][i]=tmp;}} }void prime(){memset(f,false,sizeof(f));for (int i=0;i<n;i++){dis[i]=inf;}for (int j=0;j<n;j++){dis[j]=d[0][j];}res=0;f[0]=true;for (int i=0;i<n-1;i++){int min_path=inf,min_point=0;for (int j=0;j<n;j++){if (!f[j]&&dis[j]<min_path){min_path=dis[j];min_point=j;}}f[min_point]=true;res+=min_path;for (int j=0;j<n;j++){if (!f[j]&&d[min_point][j]<dis[j]){dis[j]=d[min_point][j];}}}printf ("The highest possible quality is 1/%d.\n",res); }int main(){while(scanf ("%d",&n)!=EOF){if (n==0) break;for (int i=0;i<n;i++){scanf ("%s",x[i]);}init();prime();}return 0; } 有一個可以優化的地方，就是我們在計算距離的時候，j是可以從i+1開始的， 因為這里是一個無向圖。

2018-5-23

kruskal算法：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f using namespace std;const int N = 2000, M = 7; char p[N+1][M+1]; int f[N+1]; int n,res,cnt;struct lu{int s,e,v; }x[N*N/2];int cal(int i,int j){int sum=0;for (int k=0;k<M;k++){if (p[i][k]!=p[j][k]){sum++;}}return sum; }bool cmp(struct lu a,struct lu b){return a.v<b.v; }void init(){cnt=0;res=0;for (int i=0;i<n;i++){f[i]=i;}for (int i=0;i<n-1;i++){for (int j=i+1;j<n;j++){int tmp=cal(i,j);x[cnt].s=i;x[cnt].e=j;x[cnt].v=tmp;cnt++;}}sort(x,x+cnt,cmp); }int find(int i){int j=i;while (i!=f[i]){i=f[i];}while (j!=f[j]){j=f[j];f[j]=i;}return i; }void kruskal(){for (int i=0;i<cnt;i++){int ii=find(x[i].s),jj=find(x[i].e);if (ii!=jj){res+=x[i].v;f[ii]=f[jj]; }}printf ("The highest possible quality is 1/%d.\n",res); }int main(){while(scanf ("%d",&n)!=EOF){if (n==0) break;for (int i=0;i<n;i++){scanf ("%s",p[i]);}init();kruskal();}return 0; } 需要注意的就是并查集那邊的路徑壓縮問題。

這兩種算法的區別是，prime算法比較適用于圖邊比較多的情況，因為我們是用的鄰接矩陣存的圖，而kruskal算法比較適用于圖邊比較少的情況，因為我們是用的結構體存的圖，算法的時間復雜度與邊數有關。

總結

以上是生活随笔為你收集整理的poj1789 Truck History（最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。