最小生成ツリー(poj 1251 poj 1861 poj 1789)
9509 ワード
1.Primアルゴリズム
このアルゴリズムはDijkstraアルゴリズムとよく似ており,Dist行列のアルゴリズムに微細な差がある点が異なる.次の実装を参照してください.
PS:最初はscanfとcharを組み合わせていましたが、データ入力が各行の最後に余分なスペースがある可能性があることを調べてみました.スペース、タブ、および新しい行はドメイン分割記号として使用されますが、読み取り文字操作では一般文字で処理されます.たとえば、入力ストリーム「x y」に対して次のように呼び出されます.
scanfを使用するにはchar[]と組み合わせる必要があります.次のコードです.
2.Kruskalアルゴリズム
kruskalアルゴリズムは、合計n−1個のエッジを選択し、(合計n個の点)使用される貪欲な準則は、残りのエッジからループを生成しない最小消費量を有するエッジを選択して選択されたエッジの集合に加えることである.選択したエッジがループを生成すると、生成ツリーを形成することはできません.このアルゴリズムはよく並列調査セット,最小スタックと組み合わせて使用される.primアルゴリズムと比較するとkruskalアルゴリズムは稠密図に適用され、primアルゴリズムは疎図と稠密図に適用され、エッジの重みの記憶方式の違いに起因する.kruskalアルゴリズムは、エッジを構造配列で格納するのが一般的であるが、primアルゴリズムは、エッジの情報を2次元配列(隣接行列)で格納してもよいし、隣接テーブルで格納してもよい.
PS:この問題は私を長い間悩ませて、disscusを見てからずっとWAがojの問題だと思って、もう一つのkurskalを作るつもりはありません.必ずACを一緒にしなければなりません.次の問題の例を見て、disscusにデータをアップロードしてもテストに合格した人がいますが、提出してもずっとWAで、憂鬱で死にました.手当たり次第にまた1組のデータをテストして、確かに自分が間違っていることに気づいた.このアルゴリズムは何日も見ているので、コードに対してチェックしたくない(コードが間違っていることは知っているが)、gdbで一歩一歩デバッグして、やっと実際のスタックの操作が間違っていることに気づいた.コード注釈のところが間違っていて、実は理解しにくいが、当然間違いを犯しやすい.今回は何度も自分に自信を持たないで、WAやREが出てくるのは自分の問題だから、もっと辛抱強くしてくださいと教えてくれました.じòぴé(′▽`)じòぴééじòぴéじòぴéじòぴéじòぴéじòぴéぴéぴéぴé
このアルゴリズムはDijkstraアルゴリズムとよく似ており,Dist行列のアルゴリズムに微細な差がある点が異なる.次の実装を参照してください.
/*
poj 1251
time: 0ms
memory:220k
PS： ， scanf ， ， 。 cin 。
*/
#include <iostream>
using namespace std;
#define MaxNode 27
#define MaxEdge 150
#define INF 1000000
struct VertexEntry
{
int next, e, cost;
};
VertexEntry vertex[MaxEdge + MaxNode];
int Cost[MaxNode];
int Path[MaxNode];
int Known[MaxNode];
void Init(int Num)
{
int i, j, k = Num + 1, cost, num;
char id;
for(i = 1; i <= Num; ++i)
{
Cost[i] = INF;
Path[i] = 0;
Known[i] = 0;
vertex[i].next = 0;
}
Cost[1] = 0;
while(--Num)
{
cin >> id >> num;
i = id - '@';
while(num--)
{
cin >> id >> cost;
j = id - '@';
vertex[k].cost = cost;
vertex[k].e = j;
vertex[k].next = vertex[i].next;
vertex[i].next = k++;
vertex[k].cost = cost;
vertex[k].e = i;
vertex[k].next = vertex[j].next;
vertex[j].next = k++;
}
}
}
int Prim(int Num)
{
int i, j, min, sum = 0;
while(1)
{
min = INF;
for(i = 1; i <= Num; ++i)
{
if(!Known[i] && Cost[i] < min)
{
min = Cost[i];
j = i;
}
}
if(min == INF)
break;
Known[j] = 1;
i = j;
while(vertex[j].next)
{
j = vertex[j].next;
if(!Known[vertex[j].e] && vertex[j].cost < Cost[vertex[j].e])
{
Cost[vertex[j].e] = vertex[j].cost;
Path[vertex[j].e] = i;
}
}
}
for(i = 1; i <= Num; ++i)
{
sum += Cost[i];
}
return sum;
}
int main()
{
int Num;
cin >> Num;
while(Num)
{
Init(Num);
cout << Prim(Num) << endl;
cin >> Num;
}
return 0;
}PS:最初はscanfとcharを組み合わせていましたが、データ入力が各行の最後に余分なスペースがある可能性があることを調べてみました.スペース、タブ、および新しい行はドメイン分割記号として使用されますが、読み取り文字操作では一般文字で処理されます.たとえば、入力ストリーム「x y」に対して次のように呼び出されます.
scanf("%c%c%c",&a,&b,&c); //x a ， b ，y c scanfを使用するにはchar[]と組み合わせる必要があります.次のコードです.
/*
poj 1251
time: 0ms
memory: 220k
*/
#include <iostream>
#include <stdio.h>
using namespace std;
#define MaxNode 27
#define MaxEdge 150
#define INF 1000000
struct VertexEntry
{
int next, e, cost;
};
VertexEntry vertex[MaxEdge + MaxNode];
int Cost[MaxNode];
int Path[MaxNode];
int Known[MaxNode];
void Init(int Num)
{
int i, j, k = Num + 1, cost, num;
char id[3]; //
for(i = 1; i <= Num; ++i)
{
Cost[i] = INF;
Path[i] = 0;
Known[i] = 0;
vertex[i].next = 0;
}
Cost[1] = 0;
while(--Num)
{
scanf("%s%d", id, &num);
i = id[0] - '@'; //
while(num--)
{
scanf("%s%d", id, &cost); //
j = id[0] - '@';
vertex[k].cost = cost;
vertex[k].e = j;
vertex[k].next = vertex[i].next;
vertex[i].next = k++;
vertex[k].cost = cost;
vertex[k].e = i;
vertex[k].next = vertex[j].next;
vertex[j].next = k++;
}
}
}
int Prim(int Num)
{
int i, j, min, sum = 0;
while(1)
{
min = INF;
for(i = 1; i <= Num; ++i)
{
if(!Known[i] && Cost[i] < min)
{
min = Cost[i];
j = i;
}
}
if(min == INF)
break;
Known[j] = 1;
i = j;
while(vertex[j].next)
{
j = vertex[j].next;
if(!Known[vertex[j].e] && vertex[j].cost < Cost[vertex[j].e])
{
Cost[vertex[j].e] = vertex[j].cost;
Path[vertex[j].e] = i;
}
}
}
for(i = 1; i <= Num; ++i)
{
sum += Cost[i];
}
return sum;
}
int main()
{
int Num;
cin >> Num;
while(Num)
{
Init(Num);
cout << Prim(Num) << endl;
cin >> Num;
}
return 0;
}
2.Kruskalアルゴリズム
kruskalアルゴリズムは、合計n−1個のエッジを選択し、(合計n個の点)使用される貪欲な準則は、残りのエッジからループを生成しない最小消費量を有するエッジを選択して選択されたエッジの集合に加えることである.選択したエッジがループを生成すると、生成ツリーを形成することはできません.このアルゴリズムはよく並列調査セット,最小スタックと組み合わせて使用される.primアルゴリズムと比較するとkruskalアルゴリズムは稠密図に適用され、primアルゴリズムは疎図と稠密図に適用され、エッジの重みの記憶方式の違いに起因する.kruskalアルゴリズムは、エッジを構造配列で格納するのが一般的であるが、primアルゴリズムは、エッジの情報を2次元配列(隣接行列)で格納してもよいし、隣接テーブルで格納してもよい.
/*
poj 1861
time: 16ms
memory:428k
*/
#include <iostream>
#include <stdio.h>
using namespace std;
#define MaxNode 1001
#define MaxEdge 15001
typedef int PriorityQueue[MaxEdge];
typedef int DisjSet[MaxNode];
struct EdgeEntry
{
int n1, n2, w, flag;
};
DisjSet s; //
EdgeEntry Edge[MaxEdge];
PriorityQueue H; // ，H[i],i ，H[i] Edge index， H[i]
int max_w = 0; //
void Init(int N, int M)
{
int i, n1, n2, w;
for(i = 1; i <= N; ++i)
{
s[i] = -1;
}
for(i = 1; i <= M; ++i)
{
scanf("%d%d%d", &n1, &n2, &w);
Edge[i].n1 = n1;
Edge[i].n2 = n2;
Edge[i].w = w;
Edge[i].flag = 0;
H[i] = i; // H[i] ， Edge
}
}
int Find(int v)
{
if(s[v] < 0)
return v;
else
return s[v] = Find(s[v]);
}
void Union(int root1, int root2)
{
if(s[root1] < s[root2])
{
s[root1] += s[root2];
s[root2] = root1;
}
else
{
s[root2] += s[root1];
s[root1] = root2;
}
}
void PercolateDown(int M, int i)
{
int FirstElement = H[i];
int child;
for(; 2 * i <= M; i = child)
{
child = 2 * i;
if(2 * i + 1 <= M && Edge[H[2 * i + 1]].w < Edge[H[2 * i]].w)
++child;
if(Edge[H[child]].w < Edge[FirstElement].w) // ， FirstElement H[i], ，
H[i] = H[child];
else
break;
}
H[i] = FirstElement;
}
int DeleteMin(int M)
{
int i, child;
int MinElement = H[1];
int LastElement = H[M];
for(i = 1; i * 2 <= M; i = child)
{
child = 2 * i;
if(2 * i + 1 <= M && Edge[H[2 * i + 1]].w < Edge[H[i * 2]].w)
++child;
if(Edge[LastElement].w > Edge[H[child]].w) // ， LastElement H[i]
H[i] = H[child];
else
break;
}
H[i] = LastElement;
return MinElement;
}
void Kruskal(int N, int M)
{
int cnt = 0;
int root1, root2;
int Edgeid;
while(cnt < N - 1)
{
Edgeid = DeleteMin(M--);
root1 = Find(Edge[Edgeid].n1);
root2 = Find(Edge[Edgeid].n2);
if(root1 != root2)
{
if(Edge[Edgeid].w > max_w)
max_w = Edge[Edgeid].w;
Edge[Edgeid].flag = 1;
++cnt;
Union(root1, root2);
}
}
}
int main()
{
int N, M, i, cnt;
scanf("%d%d", &N, &M);
Init(N, M);
for(i = M / 2; i > 0; --i)
PercolateDown(M, i);
Kruskal(N, M);
printf("%d
%d
", max_w, N - 1);
for(i = 1, cnt = 0; cnt < N - 1; ++i)
{
if(Edge[i].flag)
{
++cnt;
printf("%d %d
", Edge[i].n1, Edge[i].n2);
}
}
return 0;
}PS:この問題は私を長い間悩ませて、disscusを見てからずっとWAがojの問題だと思って、もう一つのkurskalを作るつもりはありません.必ずACを一緒にしなければなりません.次の問題の例を見て、disscusにデータをアップロードしてもテストに合格した人がいますが、提出してもずっとWAで、憂鬱で死にました.手当たり次第にまた1組のデータをテストして、確かに自分が間違っていることに気づいた.このアルゴリズムは何日も見ているので、コードに対してチェックしたくない(コードが間違っていることは知っているが)、gdbで一歩一歩デバッグして、やっと実際のスタックの操作が間違っていることに気づいた.コード注釈のところが間違っていて、実は理解しにくいが、当然間違いを犯しやすい.今回は何度も自分に自信を持たないで、WAやREが出てくるのは自分の問題だから、もっと辛抱強くしてくださいと教えてくれました.じòぴé(′▽`)じòぴééじòぴéじòぴéじòぴéじòぴéじòぴéぴéぴéぴé
/*
poj 1789
time:766ms
memory:30476k
， ， prim ＋
*/
#include <stdio.h>
#include <string>
#include <iostream>
#include <stdio.h>
using namespace std;
#define MaxNode 2001
#define MaxEdge 1999001
typedef int DisjSet[MaxNode];
typedef int Priority[MaxEdge];
struct EdgeEntry
{
int n1, n2, w;
};
EdgeEntry Edge[MaxEdge];
string truck_id[MaxNode];
DisjSet s;
Priority H;
int sum;
void Init(int N, int M)
{
int i, j, n, k = 1;
for(i = 1; i <= N; ++i)
{
cin >> truck_id[i];
s[i] = -1;
}
for(i = 1; i <= M; ++i)
Edge[i].w = 0;
for(i = 1; i <= N; ++i)
for(j = 1; j < i; ++j)
{
for(n = 0; n <= 6; ++n)
Edge[k].w += (truck_id[i][n] != truck_id[j][n]);
Edge[k].n1 = i;
Edge[k].n2 = j;
H[k] = k;
++k;
}
}
int Find(int v)
{
if(s[v] < 0)
return v;
else
return s[v] = Find(s[v]);
}
void Union(int root1, int root2)
{
if(s[root1] < s[root2])
{
s[root1] += s[root2];
s[root2] = root1;
}
else
{
s[root2] += s[root1];
s[root1] = root2;
}
}
void PercolateDown(int M, int i)
{
int FirstElement = H[i];
int child;
for(; 2 * i <= M; i = child)
{
child = 2 * i;
if(2 * i + 1 <= M && Edge[H[2 * i + 1]].w < Edge[H[2 * i]].w)
++child;
if(Edge[H[child]].w < Edge[FirstElement].w)
H[i] = H[child];
else
break;
}
H[i] = FirstElement;
}
int DeleteMin(int M)
{
int i, child;
int MinElement = H[1];
int LastElement = H[M];
for(i = 1; i * 2 <= M; i = child)
{
child = 2 * i;
if(2 * i + 1 <= M && Edge[H[2 * i + 1]].w < Edge[H[i * 2]].w)
++child;
if(Edge[LastElement].w > Edge[H[child]].w)
H[i] = H[child];
else
break;
}
H[i] = LastElement;
return MinElement;
}
void Kruskal(int N, int M)
{
int cnt = 0;
int root1, root2;
int Edgeid;
while(cnt < N - 1)
{
Edgeid = DeleteMin(M--);
root1 = Find(Edge[Edgeid].n1);
root2 = Find(Edge[Edgeid].n2);
if(root1 != root2)
{
sum += Edge[Edgeid].w;
++cnt;
Union(root1, root2);
}
}
}
int main()
{
int N, M, i;
scanf("%d", &N);
while(N)
{
sum = 0;
M = (N * N - N) / 2;
Init(N, M);
for(i = M / 2; i > 0; --i)
PercolateDown(M, i);
Kruskal(N, M);
cout << "The highest possible quality is 1/" << sum << "." << endl;
scanf("%d", &N);
}
return 0;
}