Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我用kruscal和并查集结果WA#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( (-1!=s[ root1 ])&&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); double minstep; sort(edgeV.begin(),edgeV.end(),comp); while(ds.find(0)!=ds.find(1)) { minstep=edgeV[0].weight; ds.unionSets(edgeV[0].startnumber,edgeV[0].endnumber); edgeV.erase(edgeV.begin()); } printf("Scenario #%d\nFrog Distance = %.3lf\n\n",cnt++,sqrt(minstep)); edgeV.clear(); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator