昨天在老图，借得一本随机算法的书，乍一看目录，卧槽，NB了，什么都能随机……果断借走……
第一章介绍了蒙特卡罗算法和拉斯维加斯算法，Qsort就是拉斯维加斯算法，随机的结果只影响程序速度；而下面这个题，无源无汇的最小割，则是蒙特卡罗算法……随机的结果都不见得对，但是，多随机几次，得到最优解的概率会增大不少
算法很简单，在图中随机选择一条边，并将他们连接的顶点（顶点集合更为妥当……）合并，直到只剩下两个顶点集合，则这两个集合间的边至少是个割………多次随机则应该就能得到最小割了……
每次得到最小割的概率，书上证明是 2/n^2 ，可以说是相当之小……利用高等数学的知识，找不到的概率应该是1-2/n^2，于是乎，执行N^2/2次，还找不到答案的概率就是1/e……而每次随机一条边大概是O（M）的级别吧……整个算法大概是O(n*n*m)的（确切说是omega，一定是这么多次），还不保证对……
想起AC哥说过，去年FZU的B，HDU3691是这么个题，于是搞了搞，轻松拍完，样例无压力过了……之后各种TLE……毕竟300*300*50000还是压力较大的……然后各种调整随机次数，期间翻译至java……仍然TLE……一怒之下，把随机次数调整成了N次，至少能WA了……C++版本需要2400+MS，java版本需要1700+MS……（java版程序套用了我的java模板，IO是类似getchar的优化，C++是scanf，可见数据之WS……）于是把java版程序的随机次数改成5*N次，居然过了……
现在想来，数据可能水了；也可能书上理论证明的时候，放缩的太厉害，然后几百次方之后，正确率实际上比理论计算会高出很多……
无代码无真相
1 import java.util.*;
2 import java.io.*;
3 import java.math.*;
4
5
6 public class HDU3691 {
7 public static void main(String args[]) throws IOException {
8 new Prob().solve();
9 }
10 }
11
12 class Prob {
13 int[] f = new int[50010];
14 int[] t = new int[50010];
15 int[] c = new int[50010];
16 int[] fa = new int[310];
17 int n,m,tot;
18 int ans;
19 Random rand = new Random();
20
21 int find(int x) {
22 if (x == fa[x]) return x;
23 return fa[x] = find(fa[x]);
24 }
25
26 void change(int x,int y) {
27 x = find(x);
28 y = find(y);
29 fa[x] = y;
30 }
31
32 int work() {
33 for (int i = 1; i <= n; i++) {
34 fa[i] = i;
35 }
36 int cnt = n;
37 while (cnt > 2) {
38 int now = rand.nextInt(tot);
39 if (find(f[now]) == find(t[now])) {
40 int tmp = f[now]; f[now] = f[tot-1]; f[tot-1] = tmp;
41 tmp = t[now]; t[now] = t[tot-1]; t[tot-1] = tmp;
42 tmp = c[now]; c[now] = c[tot-1]; c[tot-1] = tmp;
43 tot --;
44 } else {
45 cnt --;
46 change(f[now],t[now]);
47 }
48 }
49 int ans = 0;
50 for (int i = 0; i < m; i++) {
51 if (find(f[i])!=find(t[i])) {
52 ans += c[i];
53 }
54 }
55 return ans;
56 }
57
58 final int TIMES = 5;
59
60 void solve() throws IOException {
61 MyReader in = new MyReader();
62 for (;;) {
63 n = in.nextInt();
64 m = in.nextInt();
65 tot = in.nextInt();
66 if (n + m + tot == 0) break;
67 for (int i = 0; i < m; i++) {
68 f[i] = in.nextInt();
69 t[i] = in.nextInt();
70 c[i] = in.nextInt();
71 }
72 ans = 0x7fffffff;
73 int times = TIMES * n;
74 while (times-- > 0) {
75 tot = m;
76 int tmp = work();
77 if (tmp < ans) {
78 ans = tmp;
79 }
80 }
81 System.out.println(ans);
82 }
83 }
84 void debug(Object
x) {
85 System.out.println(Arrays.deepToString(x));
86 }
87 }
88
89 class MyReader {
90 BufferedReader br = new BufferedReader (
91 new InputStreamReader (System.in));
92 StringTokenizer in;
93 String next() throws IOException {
94 if (in == null || !in.hasMoreTokens()) {
95 in = new StringTokenizer(br.readLine());
96 }
97 return in.nextToken();
98 }
99 int nextInt() throws IOException {
100 return Integer.parseInt(next());
101 }
102 }