题解 P1547 【Out of Hay】
Ajwallet
2018-02-04 08:59:29
一开始看到最小生成树,果断prim然后。。。果断WA了5个点,所以就重新审视了一下题目,发现其实只要排个序(最长边嘛),连个边(生成树嘛),就可以了。
先发个50分的。。。
```
```C++
#include<bits/stdc++.h>
#define INF 2147483648
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int l[2001][2001],n,m,x,y,z,dis[2001],minn,k,ans;//只弄了2000乘2000.。。
bool vis[2001];
int main()
{
r(i,0,2000) r(j,0,2000) l[i][j]=INF/4;
scanf("%d %d",&n,&m);
r(i,1,m)
{
scanf("%d %d %d",&x,&y,&z);if(x==y) continue;//自环判断
l[x][y]=l[y][x]=min(l[x][y],min(z,l[y][x]));//重边判断
}
r(i,1,n)
dis[i]=l[1][i];dis[1]=0;//初始化
r(i,1,n-1)
{
minn=INF/4;k=0;vis[i]=true;
r(j,1,n)
if(dis[j]<minn&&!vis[j])//找最短的
{
minn=dis[j];//赋值
k=j;//标记
}
vis[k]=true;//标记
if(!k) break;//找不到直接结束
if(minn<=INF/4) ans=max(ans,minn);//找到了才赋值
r(j,1,n)
if(l[j][k]<dis[j])//修整
dis[j]=l[j][k];
}
printf("%d",ans);//输出
}
```
代码AC
```
```C++
#include<bits/stdc++.h>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int f[2001],n,m,x,y,z,tat,ans;//tat是当前连边个数,f是并查集数组,ans是最终答案
struct node{int from,to,w;}a[20001];//结构体,等下直接排序
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}//找祖宗
void judge(int x,int y){f[find(x)]=find(y);}//连边
bool too(int x,int y){return find(x)==find(y);}//判断两个元素是否在同一集合内
bool cmp(node x,node y){return x.w<y.w;}//按按权值从小到大排(最小生成树)
int main()
{
scanf("%d%d",&n,&m);r(i,1,n) f[i]=i;//初始化
r(i,1,m)
scanf("%d %d %d",&a[i].from,&a[i].to,&a[i].w);//输入
sort(a+1,a+1+m,cmp);//排序
r(i,1,m)
if(!too(a[i].from,a[i].to))//没有连边
{
tat++;if(tat==n-1) {ans=max(ans,a[i].w);break;}//连,如果连到n-1条边就退出,最小生成树只需要n-1条边
judge(a[i].from,a[i].to);//合并
ans=max(ans,a[i].w);//统计最大值
}
printf("%d",ans);//输出
}
```