Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 第一次一遍过 ， 纪念一下。最小生成树问题-prim算法

Posted by abietic at 2017-05-16 22:26:05 on Problem 1751
#include <iostream>
#include <vector>
//----------------------------------------
using namespace std;
//----------------------------------------
struct edge
{
int power;
bool donebefore;
};
struct country
{
int x;
int y;
};
//----------------------------------------
int main()
{
int N , M;
cin >> N;
const int n = N;
country cou[n];
for (int i = 0 ; i < n ; i++)
{
cin >> cou[i].x >> cou[i].y;
}
for (int i = 0 ; i < n ; i++)
{
vector<edge> temp(n);
int nowcountry = i;
for (int j = 0 ; j < n ; j++)
{
if (j == nowcountry)
{
edge tt;
tt.power = -1;
tt.donebefore = true;
temp[j] = tt;
}
else
{
edge tt;
tt.power = (cou[nowcountry].x - cou[j].x) * (cou[nowcountry].x - cou[j].x) + (cou[nowcountry].y - cou[j].y) * (cou[nowcountry].y - cou[j].y);
tt.donebefore = false;
temp[j] = tt;
}
}
}
cin >> M;
for (int i = 0 ; i < M ; i++)
{
int from , to;
cin >> from >> to;
head[from - 1][to - 1].power = 0;
head[from - 1][to - 1].donebefore = true;
head[to - 1][from - 1].power = 0;
head[to - 1][from - 1].donebefore = true;
//cout << head[from - 1][to - 1].power << endl;
}
cout << endl;
const int INF = 210000000;
int lowcost[n];
int ver[n];
int marked[n];
for (int i = 1  ; i < n ; i++)
{
ver[i] = 0;
marked[i] = 0;
}
marked[0] = 1;
lowcost[0] = 0;
ver[0] = -1;
for (int i = 0 ; i < n - 1 ; i++)
{
int ldist = INF;
int u;
for (int j = 0 ; j < n ; j++)
{
if (lowcost[j] < ldist && marked[j] == 0)
{
ldist = lowcost[j];
u = j;
}
}
marked[u] = 1;
for (int p = 0 ; p < n ; p++)
{
if (p == u)
{
continue;
}
if (head[u][p].power < lowcost[p] && marked[p] == 0)
{
ver[p] = u;
}
}
}
for (int i = 0 ; i < n ; i++)
{
if (ver[i] != -1)
{
{
cout << ver[i] + 1 << " " << i + 1 << endl;
}
}
}
//cout << "Hello world!" << endl;
return 0;
}
//----------------------------------------

Followed by: