Note: This article is available in Chinese only. 本文暂无英文版本。
View original
URAL1416 题意：次小生成树模板题
思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。
写的时候。。因为点数是500。。我把边集的数组大小开成了500.。。交了10遍越界才意识到问题在哪里。。。真的是智商掉线啊orz…
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月11日 星期一 20时44分28秒
4File Name :code/ural/1416.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=505;
32int n,m;
33int f[N];
34int mst;
35int ans;
36int cnt = 0 ;
37vector < pi > e[N*N];
38bool flag;
39struct Edge
40{
41 int u,v;
42 int w;
43 int in;//标记边是否在生成树中。
44 bool operator < (Edge b)const
45 {
46 return w<b.w;
47 }
48 void input()
49 {
50 scanf("%d%d%d",&u,&v,&w);
51 }
52}E[N*N];
53void init()
54{
55 for ( int i = 1 ; i <= n ; i++) f[i] = i;
56 for ( int i = 1 ; i <= n ; i++) e[i].clear();
57}
58int root ( int x)
59{
60 // cout<<"x:"<<x<<" f[x]:"<<f[x]<<endl;
61 if (x!=f[x]) f[x] = root (f[x]);
62 return f[x];
63}
64void merge( int x,int y)
65{
66 int rx = root (x);
67 int ry = root (y);
68 if (rx==ry) return ;
69 f[rx] = ry;
70 // if (rx<ry) f[ry] = rx;
71 // else f[rx]=ry;
72}
73void kruskal(int k)
74{
75 for ( int i = 1 ; i <= n ; i++) f[i] = i ;
76 mst = 0 ;
77 cnt = 0;
78 for ( int i = 1; i <= m ; i++)
79 {
80 int u = E[i].u;
81 int v = E[i].v;
82 int w = E[i].w;
83 if (i==k) continue;
84 if (root(u)==root(v)) continue;
85 merge(u,v);
86 cnt++;
87 mst+=w;
88 if (cnt>=n-1) break;
89 }
90 if (cnt<n-1) return ;
91 ans = min(ans,mst);
92}
93int main()
94{
95 #ifndef ONLINE_JUDGE
96 freopen("code/in.txt","r",stdin);
97 #endif
98 cin>>n>>m;
99 init();
100 for ( int i = 1 ; i <= m ; i++)
101 {
102 E[i].input();
103 int u = E[i].u;
104 int v = E[i].v;
105 int w = E[i].w;
106
107 e[u].push_back(make_pair(v,w));
108 e[v].push_back(make_pair(u,w));
109 }
110 sort(E+1,E+m+1);
111 mst = 0 ;
112 cnt = 0 ;
113 for ( int i = 1 ; i <= m ; i++)
114 {
115 int u = E[i].u;
116 int v = E[i].v;
117 int w = E[i].w;
118 if (root(u)==root(v)) continue;
119 E[i].in = 1;
120 merge(u,v);
121 cnt++;
122 mst+=w;
123 }
124 if (cnt<n-1)
125 {
126 puts("Cost: -1");
127 puts("Cost: -1");
128 return 0;
129 }
130 printf("Cost: %d\n",mst);
131 ans = inf;
132 for ( int i = 1 ; i <= m ; i++)
133 {
134 if (E[i].in==0) continue;
135 // cout<<"hhh?"<<endl;
136 kruskal(i);
137 }
138 if (ans==inf) ans = -1;
139 printf("Cost: %d\n",ans);
140 #ifndef ONLINE_JUDGE
141 fclose(stdin);
142 #endif
143 return 0;
144}