﻿HYSBZ 1083 繁忙的都市-Ocrosoft

# HYSBZ 1083 繁忙的都市

Time Limit:10000MS     Memory Limit:165888KB     64bit IO Format:%lld & %llu

Description

Input

Output

Sample Input

```4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
```

Sample Output

`3 6`

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 10000+10
using namespace std;
struct edge
{
int u,v,w;
} edges[MAXN];
int n,m,cnt,sum,flag;
int pre[MAXN],son[MAXN];
void init()//初始化
{
for(int i=1; i<=n; i++)pre[i]=-1;
}
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int find(int x)
{
if(pre[x]!=x)pre[x]=find(pre[x]);
return pre[x];
}
bool Union(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx==fy)return false;//环
else if(son[fx]>=son[fy])
{
pre[fy]=fx;
son[fx]+=son[fy];
}
else
{
pre[fx]=fy;
son[fy]+=son[fx];
}
return true;
}
int main()
{
while(cin>>m>>n&&m)
{
swap(n,m);
cnt=0,sum=0,flag=0;
int maxx=0;
for(int i=1;i<=n;i++)
pre[i]=i,son[i]=1;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
sort(edges+1,edges+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(Union(edges[i].u,edges[i].v))
{
cnt++;
sum+=edges[i].w;
maxx=max(maxx,edges[i].w);
//printf("%d->%d\n",edges[i].u,edges[i].v);
}
if(cnt==n-1)
{
flag=1;
break;
}
}
printf("%d %d\n",cnt,maxx);
}
return 0;//
}```