社区讨论

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 条回复,欢迎继续交流。

正在加载回复...