POJ2263&&1797 最大生成树 - c++编程基础

两题都是求最大生成树中的最小值。当找到起点与终点的时候退出。
没什么陷阱，直接贴代码。
1797
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max 100000
#define inf 1<<28
using namespace std;
struct kdq
{
int s,e,l;
} line[Max];
int n,m;
int f[Max*10];
int find(int x)
{
return f[x]==x x:f[x]=find(f[x]);
}
void merge(int x,int y)
{
if(x>y)
f[x]=y;
else
f[y]=x;
}
bool cmp(kdq &a,kdq &b)
{
return a.l>b.l;
}
int kruskal()
{
int i,j;
for(i=1; i<=n+10; i++)
f[i]=i;
int ans=inf;
for(i=0; i {
int x=find(line[i].s);
int y=find(line[i].e);
if(x!=y)
{
merge(x,y);
if(ans>line[i].l)
ans=line[i].l;
if(find(1)==find(n))
return ans;
}
}
}
int main()
{
int i,j,k=0,l;
int T;
cin>>T;
int x,y,s;
while(T--)
{
k++;
cin>>n>>m;
for(i=0; i {
scanf("%d%d%d",&line[i].s,&line[i].e,&line[i].l);
}
sort(line,line+m,cmp);
printf("Scenario #%d:\n",k);
cout< }
return 0;
}
/*
1
4 2
1 3 1
3 4 2
*/
2263
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 20005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;

int n,m;
struct kdq
{
int s,e,l;
} line[Max];

bool cmp(kdq &a,kdq &b)
{
return a.l>b.l;
}
int f[Max];
void init()
{
for(int i=0; i<=n; i++)
f[i]=i;
}
int find(int x)
{
return f[x]==x x:f[x]=find(f[x]);
}
void Union(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)return ;
if(x>y)
f[x]=y;
else
f[y]=x;
}
int kruskal(int s,int e,int num)
{
init();
int ans=inf;
for(int i=0; i {
int x=find(line[i].s);
int y=find(line[i].e);
if(x!=y)
{
Union(x,y);
if(ans>line[i].l)
ans=line[i].l;
if(find(s)==find(e))
return ans;
}
}
}
int main()
{
int i,j,k,l;
int cc=0;
char aaaa[40],bbbb[40];
while(scanf("%d%d",&n,&m),(n+m))
{
mapmymap;
string a,b;
int num=1;
int num1=0;
while(m--)
{
scanf("%s%s%d",aaaa,bbbb,&l);
a=aaaa,b=bbbb;
if(!mymap[a])
{
mymap[a]=num;
num++;
}
if(!mymap[b])
{
mymap[b]=num;
num++;
}
line[num1].s=mymap[a],line[num1].e=mymap[b],line[num1].l=l;
num1++;
}
sort(line,line+num1,cmp);
scanf("%s%s",aaaa,bbbb);
a=aaaa,b=bbbb;
printf("Scenario #%d\n%d tons\n\n",++cc,kruskal(mymap[a],mymap[b],num1));
}
return 0;
}