首页 > 代码库 > hackerrank HourRank 22 Super Mancunian
hackerrank HourRank 22 Super Mancunian
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #define ll long long #define pb push_back #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define cls(name,x) memset(name,x,sizeof(name)) using namespace std; const int inf=1e9+10; const ll llinf=1e16+10; const int maxn=1e5+10; const int maxm=2e5+10; const int mod=1e9+7; const double pi=acos(-1.0); int n,m; struct edge { int st,ed,cost; bool friend operator <(const edge &a,const edge &b) { return a.cost<b.cost; } }e[maxm]; int fa[maxn]; int Find(int i) { if(i!=fa[i]) fa[i]=Find(fa[i]); return fa[i]; } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d %d",&n,&m)) { for(int i=0;i<m;i++) scanf("%d %d %d",&e[i].st,&e[i].ed,&e[i].cost); for(int i=1;i<=n;i++) fa[i]=i; sort(e,e+m); ll anscost=0; int maxcost=0; for(int i=0;i<m;i++) { int x=Find(e[i].st); int y=Find(e[i].ed); if(x!=y) { fa[x]=y; anscost+=e[i].cost; maxcost=max(maxcost,e[i].cost); } } int cnt=0; for(int i=1;i<=n;i++) fa[i]=i; for(int i=0;i<m;i++) { int x=Find(e[i].st); int y=Find(e[i].ed); if(x!=y) { if(e[i].cost<maxcost) fa[x]=y; else cnt++; } } printf("%lld %d\n",anscost-maxcost,cnt); } return 0; }
hackerrank HourRank 22 Super Mancunian
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。