题目描述

Description

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

输入描述

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

5

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

2

1 4

2 5

17

数据范围及提示

Data Size & Hint

n<=100

分类标签 Tags

 

裸prim但是我上来就智障的敲了个kruskal也是醉了

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 struct node  7 {  8     int u;  9     int v; 10     int w; 11 }edge[10001]; 12 struct ans 13 { 14     int x; 15     int y; 16 }a[10001]; 17 int num=1; 18 int f[1001]; 19 int cmp(const node &a,const node &b) 20 { 21     return a.w
         
          b.y)return 1; 38     if(a.y==b.y&&a.x
          
           i) 54 { 55 edge[num].u=i; 56 edge[num].v=j; 57 edge[num].w=p; 58 num++; 59 } 60 } 61 } 62 sort(edge+1,edge+num,cmp); 63 int k=0; 64 int tot=0; 65 int feiyong=0; 66 for(int i=1;i<=num;i++) 67 { 68 if(find(edge[i].u)!=find(edge[i].v)) 69 { 70 unionn(edge[i].u,edge[i].v); 71 //printf("%d %d\n",edge[i].u,edge[i].v); 72 if(edge[i].w!=0) 73 { 74 tot++; 75 feiyong=feiyong+edge[i].w; 76 //ans1[now]=edge[i].u; 77 //ans2[now]=edge[i].v; 78 a[now].x=min(edge[i].u,edge[i].v); 79 a[now].y=max(edge[i].u,edge[i].v); 80 k++; 81 now++; 82 } 83 84 } 85 if(k==n-1)break; 86 } 87 /*for(int i=1;i<=now;i++) 88 { 89 for(int j=i;j<=now;j++) 90 { 91 if(ans1[j]>ans1[j+1]) 92 { 93 swap(ans1[j],ans1[j+1]); 94 swap(ans1[j],ans2[j+1]); 95 } 96 } 97 }*/ 98 sort(a+1,a+now,comp); 99 printf("%d\n",tot);100 for(int i=1;i<=now-1;i++)101 {102 printf("%d %d\n",a[i].x,a[i].y);103 }104 printf("%d",feiyong);105 return 0;106 }
          
         
        
       
      
     

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 const int MAXN = 105; 5 const int INF = 2147483647; 6 int i, j, n; 7 long long ans = 0; 8 int edge[MAXN][MAXN], key[MAXN], p[MAXN], vis[MAXN] = {
   0}, //edge表示存的边 key表示权值，p表示父亲，vis表示是否已经存在已生成的树中 9         f[MAXN], l[MAXN], m = 0; //f表示头，右边表示尾10 int main() {11     cin >> n;12     for(i = 1; i <= n; i++)for(j = 1; j <= n; j++) cin >> edge[i][j];13     for(i = 1; i <= n; i++) key[i] = INF;14     key[1] = 0; //15     p[1] = 1;16     int Mini, Min;17     for(i = 0; i < n; i++) { //之需要加最多n条边，故循环n次18         Min = INF;19         for(j = 1; j <= n; j++) if(!vis[j] && key[j] < Min) {20                 Mini = j;    //找key值最小的点，即与树相邻的节点的最小权值边21                 Min = key[j];22             }23         vis[Mini] = 1; //设置访问过，即生成树已连接Mini这个节点24         ans += key[Mini];25         if(key[Mini]) {26             f[m] =   min(p[Mini], Mini); //字典序的边27             l[m++] = max(p[Mini], Mini); //同上28         }29         for(j = 1; j <= n; j++) //伪松弛，更新树临边节点的key值并维护p域30             if(!vis[j] && edge[Mini][j] < key[j]) {31                 key[j] = edge[Mini][j];32                 p[j] = Mini;33             }34     }35     cout << m << endl;36     for(i = 0; i < m; i++) cout << f[i] << ' ' << l[i] << endl;37     cout << ans;38     return 0;39 }