From The Stupid
Bad at Coding
BZOJ 1083: [SCOI2005]繁忙的都市
starli
posted @ 2016年2月14日 19:27
in 最小生成树
, 738 阅读
最小生成树求一下就好了……
其实相当于是二分一个答案然后把所有小于这个权值的边都连上然后判断连通性，但是这个过程其实就是kruscal的过程所以只要最小生成树就可以了
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010;
struct edge{int a,b,v;}e[N];
int n,m,cnt,ans,f[N];
int find(int a){return f[a]==a?a:f[a]=find(f[a]);}
void Union(int a,int b){f[find(a)]=find(b);}
bool cmp(edge a,edge b){return a.v<b.v;}
int main(){
//freopen("1083.in","r",stdin);freopen("1083.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
if(find(e[i].a)!=find(e[i].b)) cnt++,Union(e[i].a,e[i].b),ans=e[i].v;
if(cnt==n-1) break;
}
printf("%d %d",cnt,ans);
return 0;
}
2019年9月11日 19:34
HomeMaids Maintaining Services offers quite a few Warehouses, Academic institutions, Hospitals, Retail stores, Showrooms & Construction Cleaning, this will be from a minute office close to large manufacturing units. Our every staff can be fully trained in the job they can undertake selecting buffing floorboards, using scrubber driers and general cleaning on the job.
2021年9月01日 16:27
Numerous say how the cleaning company is defense to recession which is true somewhat and in certain market sectors for example office cleansing. While a few consumers within the residential marketplace may reduce cleaning throughout a downturn, a large the main clientele tend to be affluent and may afford to keep with their own service throughout a recession. Cleaning will be among the least impacted industries throughout an downturn in the economy anyway.
2021年9月19日 18:12
Currently, depending about the fabric as well as quality, a carpet might be washed by simply deep cleanup, hand wash or possibly a machine scrub. If anyone can’t discover what can be more valuable, then an experienced carpet cleanup Dubai service are able to do wonder for ones carpet.
2022年3月28日 16:47
Although, it is much better to registration and hire a cleaning agent service in the case of maintaining your personal property clean, frequently. The cleaning agent service can offer house housecleaning service about high measures guaranteeing you will always leave to a fabulous clean and additionally healthy natural world. As remarked above, it is constantly better to get aid about house cleaning agent service which usually benefits yourself and your family. A professional home cleaning company is contacted to have a fabulous dirt-free and additionally hygienic place.
2023年8月15日 16:08
Can you buy the most affordable tools, foods, clothing or whatever else? As a specialist painting company, you understand that buying low-cost tools often times will be that you're going to possibly obtain a tool 2 times, once if the cheap application breaks as well as the second time once you buy an excellent tool to restore the low-cost tool in which broke. Is cheap the most effective value? Your client thinks concerning this when considering a residence painting appraisal.