Arctic Network POJ - 2349 Kruskal
문제풀이
제목에 따라 모든 점을 연결해야 하는데 M개의 위성통신장치가 있어서 M-1개를 절약할 수 있어요. Kruskal 달리기 최소 생성 트리를 사용하고 M-1개의 큰 쪽을 빼고 나머지는 최대로 해요.
AC 코드 #include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-6;
const int MAXN = 5e2 + 10;
int M, N;
int vex[MAXN];
struct node
{
int x, y;
}a[MAXN];
struct edge
{
int u, v;
double w;
edge(int a, int b, double c) : u(a), v(b), w(c){}
bool operator < (const edge &oth) const
{
return w < oth.w;
}
};
vector<edge> ed;
double dis(int x1, int y1, int x2, int y2)
{
return sqrt((x1 - x2) * (x1 - x2) * 1.0 + (y1 - y2) * (y1 - y2) * 1.0);
}
int findr(int x)
{
return vex[x] == x ? x : vex[x] = findr(vex[x]);
}
void join(int x, int y)
{
int yy = findr(y);
int xx = findr(x);
vex[yy] = xx;
}
double kru()
{
for (int i = 0; i < N; i++)
vex[i] = i;
vector<double> vec;
for (int i = 0; i < ed.size(); i++)
if (findr(ed[i].u) != findr(ed[i].v))
{
join(ed[i].u, ed[i].v);
vec.push_back(ed[i].w);
}
double ans = 0;
for (int i = 0; i < vec.size() - M + 1; i++) // M-1
ans = max(ans, vec[i]);
return ans;
}
int main()
{
#ifdef LOCAL
freopen("C:/input.txt", "r", stdin);
#endif
int T;
cin >> T;
while (T--)
{
cin >> M >> N;
for (int i = 0; i < N; i++)
scanf("%d%d", &a[i].x, &a[i].y);
ed.clear();
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
ed.push_back(edge(i, j, dis(a[i].x, a[i].y, a[j].x, a[j].y)));
sort(ed.begin(), ed.end());
printf("%.2lf
", kru());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준]1647 도시 분할 계획(자바)
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.
길은 어느 방향으로든지 다닐 수 있는 편리한 길이다.
그리고 각 길마다 길을 유지하는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-6;
const int MAXN = 5e2 + 10;
int M, N;
int vex[MAXN];
struct node
{
int x, y;
}a[MAXN];
struct edge
{
int u, v;
double w;
edge(int a, int b, double c) : u(a), v(b), w(c){}
bool operator < (const edge &oth) const
{
return w < oth.w;
}
};
vector<edge> ed;
double dis(int x1, int y1, int x2, int y2)
{
return sqrt((x1 - x2) * (x1 - x2) * 1.0 + (y1 - y2) * (y1 - y2) * 1.0);
}
int findr(int x)
{
return vex[x] == x ? x : vex[x] = findr(vex[x]);
}
void join(int x, int y)
{
int yy = findr(y);
int xx = findr(x);
vex[yy] = xx;
}
double kru()
{
for (int i = 0; i < N; i++)
vex[i] = i;
vector<double> vec;
for (int i = 0; i < ed.size(); i++)
if (findr(ed[i].u) != findr(ed[i].v))
{
join(ed[i].u, ed[i].v);
vec.push_back(ed[i].w);
}
double ans = 0;
for (int i = 0; i < vec.size() - M + 1; i++) // M-1
ans = max(ans, vec[i]);
return ans;
}
int main()
{
#ifdef LOCAL
freopen("C:/input.txt", "r", stdin);
#endif
int T;
cin >> T;
while (T--)
{
cin >> M >> N;
for (int i = 0; i < N; i++)
scanf("%d%d", &a[i].x, &a[i].y);
ed.clear();
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
ed.push_back(edge(i, j, dis(a[i].x, a[i].y, a[j].x, a[j].y)));
sort(ed.begin(), ed.end());
printf("%.2lf
", kru());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준]1647 도시 분할 계획(자바)동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.