codevs——1003——电话连线

题目描述 Description

一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。

codevs——1003——电话连线

输入描述 Input Description

输入文件的第一行是n的值（n<=100）.

第二行至第n+1行是一个n*n的矩阵，第i行第j列的数如果为0表示城市i与城市j有电话线连接，否则为这两个城市之间的连接费用（范围不超过10000）。

输出描述 Output Description

输出文件的第一行为你连接的电话线总数m，第二行至第m+1行为你连接的每条电话线，格式为i j，（i<j）， i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出，起始点为1.

第m+2行是连接这些电话线的总费用。

样例输入 Sample Input

0 15 27 6 0

15 0 33 19 11

27 33 0 0 17

6 19 0 0 9

0 11 17 9 0

样例输出 Sample Output

1 4

2 5

数据范围及提示 Data Size & Hint

n<=100

毕竟是模板，所以必须要保存下。

至于题解，看程序就可以懂啦O(∩_∩)O哈哈~

//Asimple

//#include <bits/stdc++.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cctype>

#include <cstdlib>

#include <stack>

#include <cmath>

#include <set>

#include <map>

#include <string>

#include <queue>

#include <limits.h>

#include <time.h>

#define INF 0xfffffff

#define mod 999101

#define PI 3.14159265358979323

#define swap(a,b,t) t = a, a = b, b = t

#define CLS(a, v) memset(a, v, sizeof(a))

#define debug(a)  cout << #a << " = "  << a <<endl

#define dobug(a, b)  cout << #a << " = "  << a << " " << #b << " = " << b << endl

#define srd(a) scanf("%d", &a)

#define src(a) scanf("%c", &a)

#define srs(a) scanf("%s", a)

#define srdd(a,b) scanf("%d %d",&a, &b)

#define srddd(a,b,c) scanf("%d %d %d",&a, &b, &c)

#define prd(a) printf("%d\n", a)

#define prdd(a,b) printf("%d %d\n",a, b)

#define prs(a) printf("%s\n", a)

#define prc(a) printf("%c", a)

using namespace std;

inline int abs(int x){return x<?-x:x;}

typedef long long ll;

const int maxn = ;

int n, m, num, T, k, len, ans, sum, x, y;

int Map[maxn][maxn];

bool vis[maxn];int arr[maxn][];

void solve() {

    int Min, sum = ;

    int adv[maxn];

    int lowc[maxn];

    CLS(vis, false);

    for(int i=; i<=n; i++) lowc[i] = INF;

    lowc[] = ;

    for(int l=; l<=n; l++) {

        Min = INF;

        int index = ;

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

            if( !vis[j] && lowc[j]<Min ) {

                Min = lowc[j];

                index = j;

            }

        }

        sum += Map[adv[index]][index];

        vis[index] = true;

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

            if( !vis[i] && Map[index][i]<lowc[i]) {

                lowc[i] = Map[index][i];

                adv[i] = index;

            }

        }

        if( Min ) {

            arr[len][] = min(adv[index], index);

            arr[len][] = max(adv[index], index);

            len++;

        }

    }

    cout << len << endl;

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

        cout << arr[i][] << " " << arr[i][] << endl;

    }

    cout << sum << endl;

}

void input() {

    srd(n);

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

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

            srd(Map[i][j]);

        }

    }

    solve();

}

int main(){

    input();

    return ;

}

秒客网

codevs——1003——电话连线

相关文章