题解 P1547 【Out of Hay】

Ajwallet

2018-02-04 08:59:29

Solution

一开始看到最小生成树,果断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);//输出 } ```