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

求助1258,Agri-Net, 最小生成树,死活通不过。。。

Posted by happysongshu at 2010-04-29 14:36:08
哪位能看看吗?我自己看了好多遍都找不到问题,可提交就是Wrong Answer.
我用的是Kruskal's algorithm. 非常感谢哪!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct Edge
{
        int fiberLength;
        int nodeOne;
        int nodeTwo;
}Edge;
struct myCompare
{
        bool operator()(Edge e1, Edge e2) 
        {return e1.fiberLength<e2.fiberLength;}
} myCompare;

int main()
{
        int node, i=0,j=0, setOne = 0, setTwo = 0,sum = 0,root=0;
        cin >> node;
        int set[1000];
        Edge e;
        vector<Edge> edges;
        vector<Edge>::iterator it;
        for(i=0;i<node;i++)
        {
                set[i]=i;
                for(j=0;j<node;j++)
                {
                        cin >> e.fiberLength;
                        if(i<j)
                        {
                                e.nodeOne = i;
                                e.nodeTwo = j;
                                edges.push_back(e);
                        }
                }
        }
        sort(edges.begin(),edges.end(),myCompare);
        for(it=edges.begin(),j=0;it!=edges.end()&&j<node-1;++it)
        {
                setOne = set[(*it).nodeOne];
                setTwo = set[(*it).nodeTwo];
                if(setOne!=setTwo)
                {
                        j++;
                        sum += (*it).fiberLength;
                        root = min(setOne,setTwo);
                        for(i=0;i<node;i++)
                                if(set[i]==setOne||set[i]==setTwo)
                                {
                                        set[i]=root;
                                }
                }
        }
        cout << sum<< endl;
        return 0;
}

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