這道題我用了Kruscal+并查集算的
之前并查集用的不對,所以一直WA
并查集代碼來自我的那本寫數據結構與算法分析c++版 knuth的徒孫的網站
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#ifndef DISJ_SETS_H
#define DISJ_SETS_H
// DisjSets class
//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// int find( x ) --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed
#include <vector>
using namespace std;
/**//**
* Disjoint set class.
* Use union by rank and path compression.
* Elements in the set are numbered starting at 0.
*/
class DisjSets
{
public:
explicit DisjSets( int numElements );
int find( int x ) const;
int find( int x );
void unionSets( int root1, int root2 );
private:
vector<int> s;
};
#endif
/**//**
* Construct the disjoint sets object.
* numElements is the initial number of disjoint sets.
*/
DisjSets::DisjSets( int numElements ) : s( numElements )
{
for( int i = 0; i < s.size( ); i++ )
s[ i ] = -1;
}
/**//**
* Union two disjoint sets.
* For simplicity, we assume root1 and root2 are distinct
* and represent set names.
* root1 is the root of set 1.
* root2 is the root of set 2.
*/
void DisjSets::unionSets( int root1, int root2 )
{
// if( s[ root2 ] < s[ root1 ] ) // root2 is deeper
s[ root1 ] = root2; // Make root2 new root
//else
//{
// if( s[ root1 ] == s[ root2 ] )
// s[ root1 ]--; // Update height if same
// s[ root2 ] = root1; // Make root1 new root
//}
}
/**//**
* Perform a find.
* Error checks omitted again for simplicity.
* Return the set containing x.
*/
int DisjSets::find( int x ) const
{
if( s[ x ] < 0 )
return x;
else
return find( s[ x ] );
}
/**//**
* Perform a find with path compression.
* Error checks omitted again for simplicity.
* Return the set containing x.
*/
int DisjSets::find( int x )
{
if( s[ x ] < 0 )
return x;
else
return s[ x ] = find( s[ x ] );
}
struct Gedge
{
int startnumber;
int endnumber;
double weight;
Gedge(int s,int e,double w):startnumber(s),endnumber(e),weight(w){}
};
struct Gnode
{
int x;
int y;
Gnode(int xx,int yy):x(xx),y(yy){}
Gnode():x(0),y(0){}
static double dis(const Gnode & n1, const Gnode & n2)
{
double d1=(n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y);
return d1;
}
};
bool comp(const Gedge& g1,const Gedge& g2)
{
return g1.weight<g2.weight;
}
vector<Gedge> edgeV;
Gnode nodeArray[201];
int main()
{
int n=0,cnt=1;
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
for(int i=0;i<n;i++)
{
scanf("%d %d",&nodeArray[i].x,&nodeArray[i].y);
}
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
edgeV.push_back(Gedge(i,j,Gnode::dis(nodeArray[i],nodeArray[j])));
}
}
DisjSets ds(n+1);
double minstep=0;
sort(edgeV.begin(),edgeV.end(),comp);
while(ds.find(0)!=ds.find(1))
{
minstep=edgeV[0].weight;
int a=ds.find(edgeV[0].startnumber);
int b=ds.find(edgeV[0].endnumber);
if(a!=b)
{
ds.unionSets(a,b);
}
edgeV.erase(edgeV.begin());
}
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",cnt++,sqrt(minstep));
edgeV.clear();
}
}