블루 브리지 컵 - 젖소 위로(최소 생성 나무)
1571 단어 블루 브리지 컵
사고방식: 먼저 변의 값을 계산하고 원래의 변의 값의 두 배에 두 점의 값을 더한 다음에kruskal을 진행한다. 변수가 비교적 크기 때문에 prim을 사용하는 것이 적합하지 않다.
AC 코드:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x7fffffff
const int maxn = 100005;
int pa[maxn];
int val[maxn];
int n, m, sum;
struct node {
int u, v, val;
bool operator < (const node& a) const {
return val < a.val;
}
}edge[maxn];
int find(int x) {
return x == pa[x] ? x : pa[x] = find(pa[x]);
}
void add(int u, int v, int pri) {
edge[sum].u = u;
edge[sum].v = v;
edge[sum].val = val[u] + val[v] + pri * 2;
sum ++;
}
void kruscal() {
for(int i = 1; i <= n; i++) {
pa[i] = i;
}
int ans = 0;
for(int i = 0; i < sum; i++) {
int u = edge[i].u;
int v = edge[i].v;
int pu = find(u), pv = find(v);
if(pu == pv) continue;
ans += edge[i].val;
pa[pu] = pv;
}
int mi = INF;
for(int i = 1; i <= n; i++) {
mi = min(mi, val[i]);
}
printf("%d
", ans + mi);
}
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
sum = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
for(int i = 0; i < m; i++) {
int u, v, pri;
scanf("%d %d %d", &u, &v, &pri);
add(u, v, pri);
}
sort(edge, edge + sum);
/*for(int i = 0; i < sum; i++) {
printf("%d %d %d
", edge[i].u, edge[i].v, edge[i].val);
}*/
kruscal();
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Blu-Bridge 컵 -- Excel 주소문제 설명 Excel 셀의 주소는 열 번호를 알파벳으로 표시하는 흥미로운 것을 나타낸다. 예를 들면, A는 첫 번째 열을 나타냅니다. B는 두 번째 열을 나타냅니다. Z는 26열을 나타냅니다. AA는 27열을 나타냅...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
