Networking

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 19674   Accepted: 10061

Description

You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable that is needed to connect the points over that route. Note that there may exist many possible routes between two given points. It is assumed that the given possible routes connect (directly or indirectly) each two points in the area. 
Your task is to design the network for the area, so that there is a connection (direct or indirect) between every two points (i.e., all the points are interconnected, but not necessarily by a direct cable), and that the total length of the used cable is minimal.

Input

The input file consists of a number of data sets. Each data set defines one required network. The first line of the set contains two integers: the first defines the number P of the given points, and the second the number R of given routes between the points. The following R lines define the given routes between the points, each giving three integer numbers: the first two numbers identify the points, and the third gives the length of the route. The numbers are separated with white spaces. A data set giving only one number P=0 denotes the end of the input. The data sets are separated with an empty line. 
The maximal number of points is 50. The maximal length of a given route is 100. The number of possible routes is unlimited. The nodes are identified with integers between 1 and P (inclusive). The routes between two points i and j may be given as i j or as j i. 

Output

For each data set, print one number on a separate line that gives the total length of the cable used for the entire designed network.

Sample Input

1 0

2 3

1 2 37

2 1 17

1 2 68

3 7

1 2 19

2 3 11

3 1 7

1 3 5

2 3 89

3 1 91

1 2 32

5 7

1 2 5

2 3 7

2 4 8

4 5 11

3 5 10

1 5 6

4 2 12

0

Sample Output

0

17

16

26

Source

 
本题思路：最小生成树模版题，所以这就用了三种方法来练习自己的模版能力。
 
Kruskal算法参考代码：
 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int maxp =  + , maxr =  *  /  + ;

 int p, r, ans, head[maxp], Rank[maxp];

 struct Edge {

     int u, v, w;

 }edge[maxr];

 void Make_Set() {

     for(int i = ; i <= p; i ++) {

         head[i] = i;

         Rank[i] = ;

     }

     ans = ;

 }

 int Find(int u) {

     if(u == head[u]) return u;

     return head[u] = Find(head[u]);

 }

 void Union(int u, int v) {

     int fu = Find(u), fv = Find(v);

     if(fu == fv) return;

     if(Rank[fu] > Rank[fv])

         head[fv] = fu;

     else {

         head[fu] = fv;

         if(Rank[fu] == Rank[fv]) Rank[fv] += ;

     }

 }

 bool cmp(Edge a, Edge b) {

     return a.w < b.w;

 }

 bool Is_same(int u, int v) {

     return Find(u) == Find(v);

 }

 void Kruskal() {

     sort(edge + , edge + r + , cmp);

     int cnt = ;

     Make_Set();

     for(int i = ; i <= r; i ++) {

         if(!Is_same(edge[i].u, edge[i].v)) {

             cnt ++;

             ans += edge[i].w;

             Union(edge[i].u, edge[i].v);

         }

         if(cnt == p - ) return;

     }

 }

 int main () {

     while(~scanf("%d", &p) && p) {

         scanf("%d", &r);

         for(int i = ; i <= r; i ++) {

             scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);

         }

         Kruskal();

         printf("%d\n", ans);

     }

     return ;

 }

Prim + 邻接矩阵

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int maxp =  + , maxr =  *  /  + , INF = 0x3f3f3f3f;

 int p, r, ans, dist[maxp], G[maxp][maxp];

 bool vis[maxp];

 void Init() {

     ans = ;

     memset(vis ,false, sizeof vis);

     for(int i = ; i <= p; i ++) {

         for(int j = ; j <= p; j ++)

             G[i][j] = INF;

     }

 }

 void prim(int source) {

     dist[source] = ;

     vis[source] = true;//初始状态下只有source为已经安装了network的点

     for(int i = ; i <= p; i ++)

         dist[i] = G[source][i];//初始化所有distance为source到他们的距离

     for(int i = ; i <= p; i ++) {

         int MIN = INF, k = -;

         for(int j = ; j <= p; j ++) {//每次选择那个距离子最小生成树所有结点权值最小的结点，并将其连接Network

             if(!vis[j] && MIN > dist[j]) {

                 k = j;

                 MIN = dist[j];

             }

         }

         if(MIN == INF) return;//没找到就说明该此时已经没有可以探索的结点了

         ans += MIN;

         vis[k] = true;

         for(int j = ; j <= p; j ++) {

             if(!vis[j] && dist[j] > G[k][j])

                 dist[j] = G[k][j];//对于新增的结点k，动态更新最小生成树内结点到他们结点相邻的权值，很显然意思就是每新增一个结点就看是否此时会有一条更进的边可以到达j结点

         }

     }

 }

 int main () {

     int a, b, w;

     while(~scanf("%d", &p) && p) {

         scanf("%d", &r);

         Init();

         for(int i = ; i <= r; i ++) {

             scanf("%d %d %d", &a, &b, &w);

             if(w < G[a][b]) {//选择权值最小的那条边

                 G[a][b] = G[b][a] = w;

             }

         }

         prim();

         printf("%d\n", ans);

     }

     return ;

 }

Prim + 最小堆优化 + 邻接表

这里堆是用STL优先队列实现的，我比较懒emm...(学了这么多需要堆优化的算法，结果现在连个最基本的堆都不会写，算法导论上说斐波纳挈堆优化的Prim超级快，所以打完国赛我会总结堆 + 斐波纳挈堆

还会更新出他们优化的算法)。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

typedef pair <int, int> pii;

struct Edge {

    int to, cost;

    friend bool operator < (const Edge &a, const Edge &b) {

    return a.cost > b.cost;

    }

};

const int maxp =  + , maxr =  *  /  + , INF = 0x3f3f3f3f;

int p, r, ans, dist[maxp];

bool vis[maxp];

vector <Edge> edge[maxp];

void addedge(int u, int v, int w) {

    edge[u].push_back({v, w});

}

void Queue_Prim(int source) {

    memset(vis, false, sizeof vis);

    for(int i = ; i <= p; i ++)    dist[i] = INF;

    dist[] = ans = ;

    priority_queue <Edge> Q;

    Q.push({source, dist[source]});

    while(!Q.empty()) {

        Edge now = Q.top();

        Q.pop();

        if(vis[now.to]) continue;

        vis[now.to] = true;

        ans += now.cost;

        for(unsigned int i = ; i < edge[now.to].size(); i ++) {

            int v = edge[now.to][i].to;

            if(dist[v] > edge[now.to][i].cost) {

                dist[v] = edge[now.to][i].cost;

                Q.push({v, dist[v]});

            }

        }

    }

}

int main () {

    int a, b, c;

    while(~scanf("%d", &p) && p) {

        scanf("%d", &r);

        for(int i = ; i < r; i ++) {

            scanf("%d %d %d", &a, &b, &c);

            addedge(a, b, c);

            addedge(b, a, c);

        }

        Queue_Prim();

        for(int i = ; i <= p; i ++) edge[i].clear();

        printf("%d\n", ans);

    }

    return ;

}

最新文章

  1. [译]Object.getPrototypeOf
  2. 探索c#之不可变数据类型
  3. 【Prince2是什么】PRINCE2认证之项目四大管理步骤
  4. Nancy之基于Nancy.Hosting.Aspnet的小Demo
  5. 如何注册OCX控件
  6. 26. linux查看端口占用情况
  7. Mac Pro 修改环境变量
  8. Debian Vi 简介
  9. CSS设置滚动条样式
  10. Requirements Gathering
  11. kuangbin_UnionFind A (POJ 2236)
  12. Android IOS WebRTC 音视频开发总结（六四）-- webrtc能走多远我不知道，但这个市场真实存在
  13. 文件I/O（不带缓冲）之文件共享
  14. 开发腾讯移动游戏平台SDK ios版Ane扩展 总结
  15. 设置tomcat内存
  16. C# 导出word文档及批量导出word文档（4）
  17. iOS 之改变状态栏颜色
  18. poj 1742 coins_多重背包
  19. C++学习笔录2
  20. Delegate成员变量和Event的区别

热门文章

  1. grunt默认只允许localhost和访问，如何设置外部IP地址访问
  2. 解决Vscode编辑器不能打开多标签页问题
  3. js中JSON和JSONP的区别，让你从懵逼到恍然大悟
  4. postman断言
  5. 尖沙咀到底谁说的算？！--- CSS层叠
  6. 转载——CentOS---网络配置详解
  7. Sql Server 显示插入Identity字段
  8. Sql在Group by的select中包含多列
  9. Sql Server中的标识列(自增长字段)
  10. LA 3263 That Nice Euler Circuit(欧拉定理)