| ||||||||||
| 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 | |||||||||
求助1258,Agri-Net, 最小生成树,死活通不过。。。哪位能看看吗?我自己看了好多遍都找不到问题,可提交就是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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator