记录编号 |
405049 |
评测结果 |
AAAAAAAAAA |
题目名称 |
最优布线问题 |
最终得分 |
100 |
用户昵称 |
HeHe |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.730 s |
提交时间 |
2017-05-15 14:49:26 |
内存使用 |
0.32 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1510;
inline int in(void){
char tmp = getchar();
int res = 0;
while(!isdigit(tmp)) tmp = getchar();
while(isdigit(tmp))
res = (res + (res << 2) << 1) + (tmp ^ 48),
tmp = getchar();
return res;
}
struct DATA{
int a, b;
int val;
DATA(){;}
DATA(int _a, int _b, int _val){
a = _a, b = _b, val = _val;
}
bool operator < (const DATA& a) const {
return val < a.val;
}
};
inline bool Union(int a, int b);
int Find(int a);
int fa[MAXN];
int N, n, cnt, min_cost;
vector<DATA> data;
int main(){
#ifndef LOCAL
freopen("wire.in", "r", stdin);
freopen("wire.out", "w", stdout);
#else
freopen("test.in", "r", stdin);
#endif
n = N = in();
for(int i = 1; i <= N; ++i) fa[i] = i;
for(int i = 1, tmp; i <= N; ++i){
for(int j = 1; j <= N; ++j){
tmp = in();
if(i >= j) continue;
data.push_back(DATA(i, j, tmp));
}
}
sort(data.begin(), data.end());
while(n ^ 1 && cnt < data.size()){
int a, b, c;
do{
a = data[cnt].a;
b = data[cnt].b;
c = data[cnt].val;
++cnt;
}while(!Union(a, b));
min_cost += c;
--n;
}
printf("%d\n", min_cost);
return 0;
}
inline bool Union(int a, int b){
int x = Find(a), y = Find(b);
if(x == y) return false;
fa[x] = y;
return true;
}
int Find(int a){
if(fa[a] != a) return fa[a] = Find(fa[a]);
return a;
}