Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我用kruscal和并查集结果WA

Posted by gohan at 2007-07-28 18:14:30 on Problem 2253
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator