CodeVS/1231

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
最优布线问题	★☆☆☆☆	答案正确	100	2015-7-25 18:53:44	无

题解

CodeVS/1078改了几行就是了。

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<set>
#include<iterator>
#include<queue>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<map>
#include<cstdlib>
using namespace std;
#define foreach(i,a) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)
#define v2 pair<int,int>
#define v3 pair<int, v2 >
#define x first
#define xx x
#define yy second
#define y yy.xx
#define z yy.yy
#define m2 make_pair
#define m3(a,b,c) make_pair(a,make_pair(b,c))
#define s(x) scanf("%d",&x)
vector<int> where[100010];
vector<int> dis[100010];
void sp(v2 &p)
{
 s(p.xx);s(p.yy);
}
struct path//路径//
{
 int len;//长度//
 v2 FAT;//连接的点//
 friend bool operator<(path a, path b) { return a.len>b.len; }
 path() :len(0), FAT() {}
 path(int f, int t)
 {
  len = dis[f][t];
  FAT.xx = f;
  FAT.yy = where[f][t];
 }
};
set<int> r;//已经加入生成树的点集//
priority_queue< path  > x;//存放将要放入生成树的堆//
int main()
{
 long long totalLen = 0;
 int n,m;
 //读入数据//
 s(n);
 s(m);
 for (int i = 1;i <= m;++i)
  {
   int a,b,t;
   s(a);s(b);s(t);
   dis[a].push_back(t);
   dis[b].push_back(t);
   where[a].push_back(b);
   where[b].push_back(a);
  }
 //将与节点1相连的边插入堆//
 for (int i = 0;i < dis[1].size();++i)
  x.push(path(1, i));
 r.insert(1);//节点1放入生成树//
 while (r.size() != n&&!x.empty())//树非空//
 {
  path t = x.top();
  x.pop();
  bool ha = r.count(t.FAT.xx), hb = r.count(t.FAT.yy);
  int next = 0;
  if (!ha)next = t.FAT.xx;
  if (!hb)next = t.FAT.yy;
  if (next)
  {
   r.insert(next);//加入点//
   totalLen += t.len;
   for (int to = 0;to < dis[next].size();++to)
    if (!r.count(where[next][to]))
     x.push(path(next,to));//相连路径加入堆//
  }
 }
 cout << totalLen << endl;
}