2 条题解
-
1
使用扩展域的并查集,将每个犯人 拆成 和 两个节点,表示在同一个或不在同一个监狱。把所有边按权值从大到小排序,二分答案 ,对于每条 的边,我们尝试将两个点分在不同的监狱,若已经在同一个监狱,则矛盾。
#include <iostream> #include <algorithm> using namespace std; struct Edge { int a, b, c; bool operator<(const Edge &rhs) const { return c > rhs.c; } } edges[100005]; int fa[40005]; int n, m; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void unite(int x, int y) { fa[find(x)] = find(y); } bool valid(int mid) { for (int i = 1; i <= m; ++i) { auto [a, b, c] = edges[i]; if (c <= mid) break; if (find(a) == find(b)) return false; else unite(a + n, b), unite(a, b + n); } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n * 2; ++i) fa[i] = i; for (int i = 1; i <= m; ++i) { auto &e = edges[i]; cin >> e.a >> e.b >> e.c; } sort(edges + 1, edges + m + 1); int l = 0, r = 1e9; while (l < r) { int mid = (l + r) >> 1; if (valid(mid)) r = mid; else l = mid + 1; } cout << l << endl; return 0; }
-
1
#include <cstdio> #include <algorithm> using namespace std; struct data {int x,y,z;};//结构体便于排序的变换 data f[100005]; int n,m,a[20005],b[20005],i; inline bool cmp(data a,data b)//重写cmp函数 { return a.z>b.z; } inline int find(int x) { if(a[x]==x) return x; a[x]=find(a[x]); return a[x]; } inline void ad(int x,int y)//合并 { x=find(a[x]); y=find(a[y]); a[x]=y; } inline bool check(int x,int y)//查找 { x=find(x); y=find(y); if(x==y) return true; return false; } int main() { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) a[i]=i; for(i=1;i<=m;i++) scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z); sort(f+1,f+m+1,cmp);//c党的优越感~ for(i=1;i<=m+1;i++)//为什么m+1呢?如果运行到m+1会输出0,想想为什么。 { if(check(f[i].x,f[i].y)) {printf("%d",f[i].z);break;}//如果两个罪犯已经在同一监狱就输出 ,并退出 else { if(!b[f[i].x]) b[f[i].x]=f[i].y;//标记“敌人” else {ad(b[f[i].x],f[i].y);}//将敌人的敌人合并 if(!b[f[i].y]) b[f[i].y]=f[i].x; else {ad(b[f[i].y],f[i].x);} } } return 0; }
- 1
信息
- ID
- 524
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 38
- 已通过
- 12
- 上传者