首页 > 代码库 > UVALIVE 3939 Plucking fruits
UVALIVE 3939 Plucking fruits
并查集解决。代码跑的有够慢。应该可以通过边权排序优化。
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 1010int p[MAXN];int Find(int x) {return x == p[x] ? x : p[x] = Find(p[x]);}int N,M,R;struct node{ int u,v,w; friend bool operator < (const node &a,const node &b) { return a.w < b.w; }}src[MAXN * MAXN];bool judge(int s,int t){ int x =Find(s); int y = Find(t); if (x == y) return true; return false;}bool query(int s,int t,int least){ for (int i = 0 ; i < M ; i++) { if (src[i].w < least) continue; int x = Find(src[i].u), y = Find(src[i].v); if (x != y) p[x] = y; if (judge(s,t)) { return true; } } return false;}int main(){ int kase = 1; while (cin >> N >> M >> R) { cout << "Case " << kase++ << ‘:‘ << endl; for (int i = 0 ; i < M ;i++) cin >> src[i].u >> src[i].v >> src[i].w; for (int i = 0 ; i < R; i++) { int u ,v,w; for (int i = 0 ;i <= N ; i++) p[i] = i; cin >> u >> v >> w; if (query(u,v,w)) puts("yes"); else puts("no"); } } return 0;}
UVALIVE 3939 Plucking fruits
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。