昨天在老圖，借得一本隨機算法的書，乍一看目錄，臥槽，NB了，什么都能隨機……果斷借走……
第一章介紹了蒙特卡羅算法和拉斯維加斯算法，Qsort就是拉斯維加斯算法，隨機的結(jié)果只影響程序速度；而下面這個題，無源無匯的最小割，則是蒙特卡羅算法……隨機的結(jié)果都不見得對，但是，多隨機幾次，得到最優(yōu)解的概率會增大不少
算法很簡單，在圖中隨機選擇一條邊，并將他們連接的頂點（頂點集合更為妥當(dāng)……）合并，直到只剩下兩個頂點集合，則這兩個集合間的邊至少是個割………多次隨機則應(yīng)該就能得到最小割了……
每次得到最小割的概率，書上證明是 2/n^2 ，可以說是相當(dāng)之小……利用高等數(shù)學(xué)的知識，找不到的概率應(yīng)該是1-2/n^2，于是乎，執(zhí)行N^2/2次，還找不到答案的概率就是1/e……而每次隨機一條邊大概是O（M）的級別吧……整個算法大概是O(n*n*m)的（確切說是omega，一定是這么多次），還不保證對……
想起AC哥說過，去年FZU的B，HDU3691是這么個題，于是搞了搞，輕松拍完，樣例無壓力過了……之后各種TLE……畢竟300*300*50000還是壓力較大的……然后各種調(diào)整隨機次數(shù)，期間翻譯至java……仍然TLE……一怒之下，把隨機次數(shù)調(diào)整成了N次，至少能WA了……C++版本需要2400+MS，java版本需要1700+MS……（java版程序套用了我的java模板，IO是類似getchar的優(yōu)化，C++是scanf，可見數(shù)據(jù)之WS……）于是把java版程序的隨機次數(shù)改成5*N次，居然過了……
現(xiàn)在想來，數(shù)據(jù)可能水了；也可能書上理論證明的時候，放縮的太厲害，然后幾百次方之后，正確率實際上比理論計算會高出很多……
無代碼無真相
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 }