题目背景
AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出A地区的村庄数NN，和公路数MM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入输出格式
输入格式：
第11行两个正整数N,MN,M
下面MM行，每行33个正整数x, y, tx,y,t，告诉你这条公路连着x,yx,y两个村庄，在时间t时能修复完成这条公路。
输出格式：
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1−1，否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入样例#1： 复制
4 4 1 2 6 1 3 4 1 4 5 4 2 3
输出样例#1： 复制
#include
using
namespace
std;
//
input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
/
/
#define inf 0x3f3f3f3f
#define N 1000+1
int
mp[N][N];
int
dis[N];
int
vis[N];
int
n;
int prim(
void
) { rep(i,
1
,n) dis[i]=mp[
1][i],vis[i]=
0
; dis[
1]=
0
; rep(i,
1
,n) {
int u,minn=
inf; rep(j,
1
,n)
if(!vis[j]&&dis[j]<
minn) minn=dis[u=
j]; vis[u]=
1
; rep(j,
1
,n)
if(!vis[j]&&dis[j]>
mp[u][j]) dis[j]=
mp[u][j]; }
int ans=
0
; rep(i,
1
,n) ans=
max(ans,dis[i]);
return
ans; }
int
main() {
int
q; RII(n,q); rep(i,
1
,n) rep(j,
1
,n) mp[i][j]=
inf;
while(q--
) {
int
a,b,c; RIII(a,b,c); mp[a][b]=mp[b][a]=
c; }
int ok=
1
;
int ans=
prim();
if(ans!=
inf) printf(
"
%d\n
"
,ans);
else
printf(
"
-1
"
); }
View Code
kruskal
#include
using
namespace
std;
//
input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
/
/
#define inf 0x3f3f3f3f
#define N 1000+5
struct
node {
int
s,e,v; }s[
100005
];
int
f[N];
int
n,m;
int find1(
int
x) {
return f[x]==x?
x:find1(f[x]); }
bool
cmp(node a,node b) {
return a.v<
b.v; }
int
kruskal() {
int a,b,x=
1;
//
一开始一定要是1
int ans=
0
; sort(s+
1,s+
1+
m,cmp); rep(i,
1
,m) {
int a=
find1(s[i].s);
int b=
find1(s[i].e);
if(a==b)
continue
; ans=
max(ans,s[i].v); f[a]=
b; x++
;
if(x==n)
return ans;
//
遍历了所有的点 是时候退出了
}
if(x!=n)
return -
1;
//
说明没有最小生成树
else
return
ans; }
int
main() { RII(n,m); rep(i,
1
,n) f[i]=
i; rep(i,
1
,m) RIII(s[i].s,s[i].e,s[i].v); printf(
"
%d\n
"
,kruskal()); }
View Code
转载于:https://www.cnblogs.com/bxd123/p/10561714.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220884.html原文链接：https://javaforall.net
