Edges in MST

在用克鲁斯卡尔求MST的时候, 每个权值的边分为一类, 然后将每类的图建出来, 那些桥就是必须有的, 不是桥就不是必须有。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); struct Edge {
int a, b, id, tmp1, tmp2;
}; int n, m, fa[N], ans[N];
bool brige[N];
int dfn[N], low[N], idx;
vector<Edge> vc[N];
vector<PII> G[N]; int getRoot(int x) {
return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
} void tarjan(int u, int id) {
dfn[u] = low[u] = ++idx;
for(auto& e : G[u]) {
if(e.se == id) continue;
if(!dfn[e.fi]) {
tarjan(e.fi, e.se);
low[u] = min(low[u], low[e.fi]);
if(dfn[u] < low[e.fi]) brige[e.se] = true;
} else low[u] = min(low[u], dfn[e.fi]);
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i <= m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
vc[w].push_back(Edge{a, b, i, , });
}
for(int i = ; i <= ; i++) {
if(!SZ(vc[i])) continue;
idx = ;
for(auto& e : vc[i]) {
e.tmp1 = getRoot(e.a);
e.tmp2 = getRoot(e.b);
if(e.tmp1 > e.tmp2) swap(e.tmp1, e.tmp2);
}
for(auto& e : vc[i]) {
if(e.tmp1 == e.tmp2) {
ans[e.id] = ;
} else {
G[e.tmp1].clear();
G[e.tmp2].clear();
dfn[e.tmp1] = dfn[e.tmp2] = ;
}
}
for(auto& e : vc[i]) {
if(e.tmp1 != e.tmp2) {
G[e.tmp1].push_back(mk(e.tmp2, e.id));
G[e.tmp2].push_back(mk(e.tmp1, e.id));
}
}
for(auto& e : vc[i]) {
if(e.tmp1 != e.tmp2) {
if(!dfn[e.tmp1]) tarjan(e.tmp1, );
if(!dfn[e.tmp2]) tarjan(e.tmp2, );
}
}
for(auto& e : vc[i]) {
if(e.tmp1 != e.tmp2) {
if(brige[e.id]) ans[e.id] = ;
else ans[e.id] = ;
}
}
for(auto& e : vc[i]) {
int x = getRoot(e.a);
int y = getRoot(e.b);
if(x != y) fa[x] = y;
}
}
for(int i = ; i <= m; i++) {
if(ans[i] == ) puts("any");
else if(ans[i] == ) puts("at least one");
else puts("none");
}
return ;
} /*
*/

最新文章

  1. [备忘] Automatically reset Windows Update components
  2. jupyter nb + scite 混合搭建成我的最爱IDE
  3. IOS TableView 去除点击后产生的灰色背景
  4. iOS开发如何学习前端
  5. Spring Remoting: HTTP Invoker--转
  6. java post请求
  7. 巴科斯范式和sql语言
  8. 苹果推送APNS自己总结
  9. RedHat安装VMwareTools出现解压压缩包时无法打开文件的现象
  10. skinned mesh 蜘蛛样
  11. ISO 9141-2 and ISO 14230-2 INITIALIZATION and DATA TRANSFER
  12. ABAP程序执行效率和优化 ABAP Performance Examples
  13. Android Paint和Color类
  14. Linux Kernel 排程機制介紹
  15. 浩哥解析MyBatis源码(二)——Environment环境
  16. 《Head First Java》读书笔记(1) - Java语言基础
  17. linux虚拟机 在install yum时提示无法获得锁 var/lib/dekg/lock时该如何解决?
  18. 系统架构-设计模式(适配器、观察者、代理、抽象工厂等)及架构模式(C/S、B/S、分布式、SOA、SaaS)(干货)
  19. JSON.stringify转化报错
  20. Java IO的一些列子

热门文章

  1. 在Eclipse中利用maven整合搭建ssm框架
  2. 12. SpringBoot国际化
  3. 使用 Parallel LINQ 进行数据分页
  4. 虚拟机centos7系统下安装hadoop ha和yarn ha(详细)
  5. 设计模式之UML类图六大关系辨析【2】
  6. 寻路优化(二)——二维地图上theta*算法的设计探索
  7. 使用Jupyter lab前应该读的几篇文章
  8. sqlalchemy-查询
  9. php 全局变量问题
  10. 在iOS 开发中用GDataXML(DOM方式)解析xml文件