さいしょうせいせいツリーアルゴリズム
12180 ワード
今日dijsktraを復習するついでに最小生成ツリーを求めるいくつかのアルゴリズムを学びました.最小生成ツリーを求めるには多くのアルゴリズムがあります.このうち,複数のアルゴリズムは最小生成ツリーのMST特性を用いている:G=(V,E)が接続網であり,Uが頂点Vの非空子セットであると仮定する.(u,v)が最小重み値を有するエッジであり、uがUに属し、vがV−Uに属する場合、エッジ(u,v)を含むツリーが必ず存在する.ここではまずこの性質を用いたprimアルゴリズムについて述べる.
primアルゴリズムのアルゴリズム思想は,G=(V,E)がネットワークに接続され,T=(U,TE)が予め構成された最小生成ツリー,TEが最小生成ツリーのエッジの集合,Uが頂点集合であると仮定する.TE=空セットとU={u 0},u 0がVに属することから,すべてのuがUに属し,vがV-Uに属するエッジ(u,v)がEに属し,代価が最小の(u,v)を探して集合TEに押し込むとともに,vがU=VになるまでTEにn-1辺が必要である場合,T=(V,TE)はNの最小生成ツリーとなる.
Primは通常の2次元配列で実現でき,早ければ優先キュー+2次元配列で実現できる.優先キューが実現されると,1つの構造体で点の和点から前点までの距離が格納される.優先キューのプロパティを使用すると、前のポイントの重み値が最も小さく、探していないポイントが毎回返されます.次にlowcost[]配列を用いて優先キューの値を更新し,すべてが検索されたことを知る.
アルゴリズムは線形テーブルで実現できます.ここでは例題を見ます.
nyoj 38配線問題標準のテンプレート問題、コード:
次に、優先キューの実装を見てみましょう.この問題は優先キューと実行時間の差は大きくありません.優先キューが速く、コードを見ていると言えます.
また最小生成数を求める別のアルゴリズムを学習し,まずこのアルゴリズムの考え方:まず,1つの連通図G=(V,E)の各頂点を1つの連通成分とし,最小生成木の初期状態はn個の頂点のみがエッジを持たない非連通図T=(V,{})とし,Eの中で代価が最小のエッジを選択するたびに,この辺に付随する頂点がそれぞれTの異なる連通成分にある場合、この辺をTに加える.そうでなければ、この辺を捨てて次の代価の最小の辺を選択し、Tのすべての頂点が連通成分である最小生成ツリーを構成するまで.
primと何が違うのでしょうか.primは任意の点から接続された最小のエッジを探すたびに、n-1エッジを形成して最小生成ツリーを形成しますが、kruskalは頂点から始まるのではなく、最小のエッジを探すたびに、このエッジに依存する頂点が2つの異なる連通成分にあるかどうかを判断します.そうすれば参加します.すべての点が連通成分を構成するまで.
しかし、ここで最も核心的な一歩は、1つのエッジに依存する2つの頂点が異なる2つの連通成分にあるかどうかを判断することであり、ここでは別のアルゴリズムを用いて、セットを調べるので、私はkruskalの思想を勉強した後、すぐに併差セットを勉強しました.また,コレクションを調べるのもよく使われる基礎アルゴリズムであり,学習する必要がある.
このリンクを見ることができます:はっきり言っています.まず、テンプレートのタイトルを見てみましょう.1160-X-Plosivesコード:
セットのこの特性に基づいてkruskalアルゴリズムをよく書くことができます.ここではテンプレートのテーマを示します.
10369-Arctic Networkはテーマを理解していませんが、他の人の翻訳を見ると最小生成ツリーのs-p小重み値を求める辺で、ここで辺の重み値をソートするときに間接的なソートを運用して、分からないのは自分で負けて見ることができて、確かにすばらしいです.実は当初私が考えたのは優先キューで毎回出力の最小の辺を実現することができるかどうかで、意外にもこのようにすることができて、順序は構造体さえ節約して、まだよく勉強しなければならないようで、くだらないことを言わないで、コード:
Picnic Planning
Time Limit: 5000MS
Memory Limit: 10000K
Total Submissions: 8021
Accepted: 2822
Description
The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on everyone's cars (thus saving gas, wear and tear, etc.). To this end they are willing to cram themselves into as few cars as necessary to minimize the total number of miles put on all their cars together. This often results in many brothers driving to one brother's house, leaving all but one car there and piling into the remaining one. There is a constraint at the park, however: the parking lot at the picnic site can only hold a limited number of cars, so that must be factored into the overall miserly calculation. Also, due to an entrance fee to the park, once any brother's car arrives at the park it is there to stay; he will not drop off his passengers and then leave to pick up other brothers. Now for your average circus clan, solving this problem is a challenge, so it is left to you to write a program to solve their milage minimization problem.
Input
Input will consist of one problem instance. The first line will contain a single integer n indicating the number of highway connections between brothers or between brothers and the park. The next n lines will contain one connection per line, of the form name1 name2 dist, where name1 and name2 are either the names of two brothers or the word Park and a brother's name (in either order), and dist is the integer distance between them. These roads will all be 2-way roads, and dist will always be positive.The maximum number of brothers will be 20 and the maximumlength of any name will be 10 characters.Following these n lines will be one final line containing an integer s which specifies the number of cars which can fit in the parking lot of the picnic site. You may assume that there is a path from every brother's house to the park and that a solution exists for each problem instance.
Output
Output should consist of one line of the form
Total miles driven: xxx
where xxx is the total number of miles driven by all the brothers' cars.
Sample Input
Sample Output
Source
primアルゴリズム...書き‐かけだ
primアルゴリズムのアルゴリズム思想は,G=(V,E)がネットワークに接続され,T=(U,TE)が予め構成された最小生成ツリー,TEが最小生成ツリーのエッジの集合,Uが頂点集合であると仮定する.TE=空セットとU={u 0},u 0がVに属することから,すべてのuがUに属し,vがV-Uに属するエッジ(u,v)がEに属し,代価が最小の(u,v)を探して集合TEに押し込むとともに,vがU=VになるまでTEにn-1辺が必要である場合,T=(V,TE)はNの最小生成ツリーとなる.
Primは通常の2次元配列で実現でき,早ければ優先キュー+2次元配列で実現できる.優先キューが実現されると,1つの構造体で点の和点から前点までの距離が格納される.優先キューのプロパティを使用すると、前のポイントの重み値が最も小さく、探していないポイントが毎回返されます.次にlowcost[]配列を用いて優先キューの値を更新し,すべてが検索されたことを知る.
アルゴリズムは線形テーブルで実現できます.ここでは例題を見ます.
nyoj 38配線問題標準のテンプレート問題、コード:
#include <stdio.h>
#include <string.h>
#define inf 9999999
#define MAX 510
int map[MAX][MAX]; //
int vis[MAX],lowcost[MAX]; //
int T,v,e;
int Prim(int x)
{
memset(vis,0,sizeof(vis));
memset(lowcost,-1,sizeof(lowcost));
int ans=0;
for(int i=1;i<=v;i++)
lowcost[i]=map[x][i];
lowcost[x]=0;
vis[x]=1;
int k=x;
for(int i=1;i<v;i++)
{
int Smin=inf;
for(int j=1;j<=v;j++) // ，
{
if(!vis[j]&&lowcost[j]&&lowcost[j]<Smin){
k=j;Smin=lowcost[j];
}
}
ans+=lowcost[k];
vis[k]=1;
for(int j=1;j<=v;j++) // lowcost ，
{
if(!vis[j]&&map[k][j]&&map[k][j]<lowcost[j])
lowcost[j]=map[k][j];
}
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
int a,b,c,d;
memset(map,0,sizeof(map));
scanf("%d%d",&v,&e);
for(int i=0;i<e;i++){
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]){
if(map[a][b]>c)
{
map[a][b]=map[b][a]=c;
}
}
else
map[a][b]=map[b][a]=c;
}
int Min=inf;
for(int i=1;i<=v;i++){
scanf("%d",&d);
if(d<Min)
Min=d;
}
printf("%d
",Min+Prim(1));
}
return 0;
}
次に、優先キューの実装を見てみましょう.この問題は優先キューと実行時間の差は大きくありません.優先キューが速く、コードを見ていると言えます.
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#define inf 9999999
#define MAX 510
using namespace std;
int map[MAX][MAX];
int vis[MAX],lowcost[MAX];
int T,v,e;
struct Info // ，
{
int ve; //
int dis; //
bool operator < (const Info &a) const //
{
return a.dis<dis;
}
};
int Prim(int start)
{
int ans=0;
memset(vis,0,sizeof(vis));
memset(lowcost,inf,sizeof(lowcost));
Info pre, cur;
priority_queue<Info> Q;
lowcost[start] = 0;
pre.dis = 0;
pre.ve = start;
Q.push( pre );
while( !Q.empty() )
{
pre = Q.top();
Q.pop();
if( vis[pre.ve] ) // ，
continue;
ans += pre.dis;
vis[pre.ve] = 1;
for( int i = 1; i <= v; i++ )
{
if( !vis[i] && map[pre.ve][i] < lowcost[i] ) //
{
lowcost[i] = map[pre.ve][i];
cur.dis = lowcost[i];
cur.ve = i;
Q.push( cur );
}
}
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--)
{
int a,b,c,d;
memset(map,inf,sizeof(map));
scanf("%d%d",&v,&e);
for(int i=0;i<e;i++){
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]){
if(map[a][b]>c)
{
map[a][b]=map[b][a]=c;
}
}
else
map[a][b]=map[b][a]=c;
}
int Min=inf;
for(int i=1;i<=v;i++){
scanf("%d",&d);
if(d<Min)
Min=d;
//printf("%d",d);
}
printf("%d
",Min+Prim(1));
}
return 0;
}
また最小生成数を求める別のアルゴリズムを学習し,まずこのアルゴリズムの考え方:まず,1つの連通図G=(V,E)の各頂点を1つの連通成分とし,最小生成木の初期状態はn個の頂点のみがエッジを持たない非連通図T=(V,{})とし,Eの中で代価が最小のエッジを選択するたびに,この辺に付随する頂点がそれぞれTの異なる連通成分にある場合、この辺をTに加える.そうでなければ、この辺を捨てて次の代価の最小の辺を選択し、Tのすべての頂点が連通成分である最小生成ツリーを構成するまで.
primと何が違うのでしょうか.primは任意の点から接続された最小のエッジを探すたびに、n-1エッジを形成して最小生成ツリーを形成しますが、kruskalは頂点から始まるのではなく、最小のエッジを探すたびに、このエッジに依存する頂点が2つの異なる連通成分にあるかどうかを判断します.そうすれば参加します.すべての点が連通成分を構成するまで.
しかし、ここで最も核心的な一歩は、1つのエッジに依存する2つの頂点が異なる2つの連通成分にあるかどうかを判断することであり、ここでは別のアルゴリズムを用いて、セットを調べるので、私はkruskalの思想を勉強した後、すぐに併差セットを勉強しました.また,コレクションを調べるのもよく使われる基礎アルゴリズムであり,学習する必要がある.
このリンクを見ることができます:はっきり言っています.まず、テンプレートのタイトルを見てみましょう.1160-X-Plosivesコード:
#include <cstdio>
using namespace std;
const int maxn = 100010;
int pa[maxn];
int find(int x)
{
// ， . ， 。
return pa[x] != x ? pa[x]=find(pa[x]) : x;
}
int main()
{
int x, y;
while(~scanf("%d", &x))
{
for(int i = 0; i < 100001; i++) pa[i] = i; //
int ans = 0;
while(x != -1)
{
scanf("%d", &y);
x = find(x), y = find(y);
if(x != y) pa[x] = y; //
else ans++;
scanf("%d", &x);
}
printf("%d
", ans);
}
return 0;
}
セットのこの特性に基づいてkruskalアルゴリズムをよく書くことができます.ここではテンプレートのテーマを示します.
10369-Arctic Networkはテーマを理解していませんが、他の人の翻訳を見ると最小生成ツリーのs-p小重み値を求める辺で、ここで辺の重み値をソートするときに間接的なソートを運用して、分からないのは自分で負けて見ることができて、確かにすばらしいです.実は当初私が考えたのは優先キューで毎回出力の最小の辺を実現することができるかどうかで、意外にもこのようにすることができて、順序は構造体さえ節約して、まだよく勉強しなければならないようで、くだらないことを言わないで、コード:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 500
#define M 200000
int n, m, t, dot[N][2];
int v[M], u[M], r[M], p[M];
double w[M];
void init()
{
int dx, dy;
scanf("%d%d",&t,&n);
for(int i = 0; i < n; i++)
scanf("%d%d",&dot[i][0],&dot[i][1]);
m = 0;
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{
dx = dot[i][0]-dot[j][0]; dy = dot[i][1]-dot[j][1];
w[m] = sqrt(dx*dx+dy*dy);
u[m] = i;
v[m] = j;
m++;
}
}
int cmp(const int i, const int j) { return w[i]<w[j]; }
int find(int x) { return p[x]==x?x:p[x] = find(p[x]); }
double kruskal()
{
int cnt = 0;
for(int i = 0; i < n; i++) p[i] = i;
for(int i = 0; i < m; i++) r[i] = i;
sort(r,r+m,cmp);
for(int i = 0; i < m; i++)
{
int e = r[i];
int x = find(u[e]); int y = find(v[e]);
if(x!=y)
{
if(++cnt==n-t) return w[e];
p[x] = y;
}
}
return 0.0;
}
int main ()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
init();
printf("%.2lf
",kruskal());
}
return 0;
}
Picnic Planning
Time Limit: 5000MS
Memory Limit: 10000K
Total Submissions: 8021
Accepted: 2822
Description
The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on everyone's cars (thus saving gas, wear and tear, etc.). To this end they are willing to cram themselves into as few cars as necessary to minimize the total number of miles put on all their cars together. This often results in many brothers driving to one brother's house, leaving all but one car there and piling into the remaining one. There is a constraint at the park, however: the parking lot at the picnic site can only hold a limited number of cars, so that must be factored into the overall miserly calculation. Also, due to an entrance fee to the park, once any brother's car arrives at the park it is there to stay; he will not drop off his passengers and then leave to pick up other brothers. Now for your average circus clan, solving this problem is a challenge, so it is left to you to write a program to solve their milage minimization problem.
Input
Input will consist of one problem instance. The first line will contain a single integer n indicating the number of highway connections between brothers or between brothers and the park. The next n lines will contain one connection per line, of the form name1 name2 dist, where name1 and name2 are either the names of two brothers or the word Park and a brother's name (in either order), and dist is the integer distance between them. These roads will all be 2-way roads, and dist will always be positive.The maximum number of brothers will be 20 and the maximumlength of any name will be 10 characters.Following these n lines will be one final line containing an integer s which specifies the number of cars which can fit in the parking lot of the picnic site. You may assume that there is a path from every brother's house to the park and that a solution exists for each problem instance.
Output
Output should consist of one line of the form
Total miles driven: xxx
where xxx is the total number of miles driven by all the brothers' cars.
Sample Input
10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3Sample Output
Total miles driven: 183Source
primアルゴリズム...書き‐かけだ
#include <iostream>
#include<string.h>
using namespace std;
const int mmax=21;
const int max=9999999;
struct Node
{
int sv,ev;
int w; //
}；
int n,s,nv,ans,flag; //nv ，n
char vdes[mmax][12];
int vis[mmax],map[mmax][mmax];
Node mst[mmax-1];
int Verind(char* name);
int Mstbyprim();
void Maxweight(int mv,int sv,int ev,int& maxw,int& ind);
void Solve();
int main()
{
char namel[12],name2[12];
int dist,i,j;
for(i=0;i<mmax;i++)
{
for(j=0;j<mmax;j++)
map[i][j]=max;
}
nv=0;
cin>>n;
strcpy(vdes[nv],"Park");nv++:
for(i=0;i<n;i++)
{
cin>>name1>>name2>>dist;
int ind1=Verind(name1),ind2=Verind2(name2);
map[ind1][ind2]=map[ind2][ind1]=dist;
}
cin>>s;//
Solve();
cout<<"Total miles driven: "<<ans<<endl;
return 0;
}
int Verind(char* name)
{
int ind=0;
while(ind<nv && strcmp(vdes[ind],name)!=0)
ind++;
if(ind==nv)
{
strcmp(vdes[nv],name);nv++;
}
}
int Mstbyprim()
{
int mstws=0;
int i,j,k;
for(i=0;i<nv-1;i++)
{
mst[i].sv=1;mst[i].ev=i+1;mst[i].w=map[1][i+1];
}
for(k=2;k<nv;k++)
{
int minw=mst[k-1].w,ind=k-1;
for(j=k;j<nv-1;j++)
{
if(mst[j].w<minw)
minw=mst[j].w;ind=j;
}
mstws+=minw;
Node tmp=mst[k-1];mst[k-1]=mst[ind];mst[ind]=temp;
j=mst[k-1].ev;for(i=k;i<nv-1;i++)
{
int v=mst[i].ev,w=map[j][v];
if(w<mst[i].w)
mst[i].w=w;mst[i].sv=j;
}
}
return mstws;
}
void Maxweight(int mv,int sv,int ev,int& maxw,int& ind)
{
if(ev>mv)
{
}
}