社区讨论
RE求助
P1550[USACO08OCT] Watering Hole G参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo27m3jf
- 此快照首次捕获于
- 2023/10/23 09:19 2 年前
- 此快照最后确认于
- 2023/11/03 09:33 2 年前
CPP
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define in int /*long long*/
#define ri register int /*long long*/
#define maxn 100005
using namespace std;
in n,m;
in w[maxn];
in p[305][305];
inline in read()
{
in x=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
ff=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*ff;
}
inline void write(in x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
inline void write_space(in x)
{
write(x);putchar(32);
}
inline void write_line(in x)
{
write(x);putchar(10);
}
in fa[1000];
struct node {
in u,v,w;
}path[1005];
in find(in x){
if(fa[x] == x) return x;
else {
fa[x] = find(fa[x]);
return fa[x];
}
}
bool cmp(node a,node b){
if(a.w > b.w) return 0;
else return 1;
}
in mp[1000][1000];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n = read();
in cnt = 1;
for(in i = 1 ; i <= n ; i ++){
path[cnt].u = i;
path[cnt].v = n + 1;
path[cnt].w = read();
cnt ++;
}
for(in i = 1 ; i <= n ; i ++){
for(in j = 1 ; j <= n ; j ++){
mp[i][j] = read();
}
}
for(in i = 1 ; i <= n ; i ++){
for(in j = 1 ; j <= n ; j ++){
if(i == j)
continue;
path[cnt].u = i;
path[cnt].v = j;
path[cnt].w = mp[i][j];
cnt ++;
}
}
for(in i = 1 ; i <= n + 1 ; i ++)
fa[i] = i;
sort(path + 1,path + 1 + cnt,cmp);
in ans = 0;
for(in i = 1 ; i <= cnt ; i ++){
if(find(path[i].u) != find(path[i].v)){
fa[fa[path[i].u]] = fa[path[i].v];
ans += path[i].w;
}
}
cout << ans;
//fclose(stdin);QAQ
//fclose(stdout);
system("pause");
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...