已过,求助快读哪里错了
查看原帖
已过,求助快读哪里错了
307940
aaaaaaaawsl楼主2022/11/24 08:29

快读是用了好久的板子, 但是在这道题上面会死在read,真的不理解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

namespace FastIO {
    char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
    long long p, p3 = -1;
    void read() {}
    void print() {}
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline void flush(){
        fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
    }
    template <typename T, typename... T2>
    inline void read(T &x, T2 &...oth) {
        long long f = 0;
        x = 0;
        char ch = getc();
        while (!isdigit(ch)) {
            if (ch == '-') f = 1;
            ch = getc();
        }
        while (isdigit(ch)) {
            x = (x << 1) + (x << 3) + (ch ^ '0');
            ch = getc();
        }
        x = f ? -x : x;
        read(oth...);
    }
    template <typename T, typename... T2>
    inline void print(T x, T2... oth) { 
        if (p3 > 1 << 20) 
            flush();
        if (x < 0)
            buf2[++p3] = 45, x = -x; 
        do {
            a[++p] = x % 10 + 48;
        } while (x /= 10);
        do {
            buf2[++p3] = a[p];
        } while (--p);
        buf2[++p3] = hh; 
        print(oth...);
    }
}
#define read FastIO::read
#define print FastIO::print

const int N = 5e3 + 10; 
int n, m, cnt, ans;

struct node{
	int x; int y; int val;
	inline bool operator < (const node &a) const {
		return a.val < val;
	}
};

priority_queue<node> q;

int fa[N];
int fd(int now){
	return (now == fa[now] ? now : fa[now] = fd(fa[now]));
}

void kruskal(){
	for(int i = 1; i <= m; ++ i){
		node tp = q.top();
		q.pop();
		int x = fd(tp.x), y = fd(tp.y);
		if(x == y) continue;
		ans += tp.val;
		fa[x] = y;
		if(++ cnt == n - 1) break;
	}
}

int main(){
//	freopen("1.txt", "r", stdin);
	read(n); read(m);
	for(int i = 1; i <= n; ++ i) fa[i] = i;
	for(int i = 1; i <= m; ++ i){
		int a, b, c;
		read(a); read(b); read(c);
		q.push(node{a, b, c});
	}
	kruskal();
	if(cnt < n - 1) printf("orz");
	else printf("%d", ans);
	return 0;
}
2022/11/24 08:29
加载中...