ural 1416. Confidential (次小生成树模板题)

2016年7月12日 0 作者 CrazyKK

URAL1416
题意：次小生成树模板题

思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。

 

写的时候。。因为点数是500。。我把边集的数组大小开成了500.。。交了10遍越界才意识到问题在哪里。。。真的是智商掉线啊orz…

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年07月11日 星期一 20时44分28秒
File Name :code/ural/1416.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=505;
int n,m;
int f[N];
int mst;
int ans;
int cnt = 0 ;
vector < pi > e[N*N];
bool flag;
struct Edge
{
    int u,v;
    int w;
    int in;//标记边是否在生成树中。
    bool operator < (Edge b)const
    {
        return w<b.w;
    }
    void input()
    {
        scanf("%d%d%d",&u,&v,&w);
    }
}E[N*N];
void init()
{
    for ( int i = 1 ; i <= n ; i++) f[i] = i;
    for ( int i = 1 ; i <= n ; i++) e[i].clear();
}
int root ( int x)
{
  //  cout<<"x:"<<x<<" f[x]:"<<f[x]<<endl;
    if (x!=f[x]) f[x] = root (f[x]);
    return f[x];
}
void merge( int x,int y)
{
    int rx = root (x);
    int ry = root (y);
    if (rx==ry) return ;
    f[rx] = ry;
  //  if (rx<ry) f[ry] = rx;
  //  else f[rx]=ry;
}
void kruskal(int k)
{
    for ( int i = 1 ; i <= n ; i++) f[i] = i ;
    mst = 0 ;
    cnt =  0;
    for ( int i = 1; i <= m ; i++)
    {
        int u = E[i].u;
        int v = E[i].v;
        int w = E[i].w;
        if (i==k) continue;
        if (root(u)==root(v)) continue;
        merge(u,v);
        cnt++;
        mst+=w;
        if (cnt>=n-1) break;
    }
    if (cnt<n-1) return ;
    ans = min(ans,mst);
}
int main()
{
        #ifndef  ONLINE_JUDGE
        freopen("code/in.txt","r",stdin);
  #endif
        cin>>n>>m;
        init();
        for ( int i = 1 ; i <= m ; i++)
        {
            E[i].input();
            int u = E[i].u;
            int v = E[i].v;
            int w = E[i].w;
 
            e[u].push_back(make_pair(v,w));
            e[v].push_back(make_pair(u,w));
        }
        sort(E+1,E+m+1);
        mst = 0 ;
        cnt = 0 ;
        for ( int i = 1 ; i <= m ; i++)
        {
            int u = E[i].u;
            int v = E[i].v;
            int w = E[i].w;
            if (root(u)==root(v)) continue;
            E[i].in = 1;
            merge(u,v);
            cnt++;
            mst+=w;
        }
        if (cnt<n-1)
        {
            puts("Cost: -1");
            puts("Cost: -1");
            return 0;
        }
        printf("Cost: %d\n",mst);
        ans = inf;
        for ( int i = 1 ; i <= m ; i++)
        {
            if (E[i].in==0) continue;
           // cout<<"hhh?"<<endl;
            kruskal(i);
        }
        if (ans==inf) ans = -1;
        printf("Cost: %d\n",ans);
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

 

分类目录模板题 算法学习
标签mst 次小生成树

关于作者

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz