PKU_campus_2018_D Chocolate

思路：
题目链接http://poj.openjudge.cn/practice/C18D/
kruskal过程中使用乘法原理计数。
实现：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int MAXN = 405, INF = 0x3f3f3f3f;
 5 const ll MOD = 1e9 + 7;
 6 string s[MAXN];
 7 int d[MAXN][MAXN];
 8 int par[MAXN]; 
 9 ll num[MAXN];
10 struct edge
11 {
12     int a, b, l;
13 };
14 edge es[MAXN * MAXN];
15 void init(int n)
16 {
17     for (int i = 0; i < n; i++) { par[i] = i; num[i] = 1; }
18 }
19 int find(int x)
20 {
21     if (par[x] == x) return x;
22     return par[x] = find(par[x]);
23 }
24 int uni(int x, int y)
25 {
26     x = find(x); y = find(y);
27     if (x == y) return x;
28     par[x] = y; return y;
29 }
30 int edit_dis(string a, string b)
31 {
32     int la = a.length(), lb = b.length();
33     for (int i = 0; i <= la; i++) d[i][0] = i;
34     for (int i = 0; i <= lb; i++) d[0][i] = i;
35     for (int i = 1; i <= la; i++)
36     {
37         for (int j = 1; j <= lb; j++)
38         {
39             if (a[i - 1] == b[j - 1]) d[i][j] = d[i - 1][j - 1];
40             else d[i][j] = min(d[i][j - 1], d[i - 1][j]) + 1;
41         }
42     }
43     return d[la][lb];
44 }
45 bool cmp(edge & x, edge & y)
46 {
47     return x.l < y.l;
48 }
49 bool check(int x, int cnt)
50 {
51     int minn = INF, maxn = -INF;
52     for (int i = 0; i < cnt; i++)
53     {
54         int px = find(es[i].a), py = find(es[i].b);
55         if (px == x && py == x) maxn = max(maxn, es[i].l);
56         else if ((px == x && py != x) || (px != x && py == x))
57             minn = min(minn, es[i].l);
58     }
59     return maxn < minn;
60 }
61 int main()
62 {
63     int t, n;
64     cin >> t;
65     while (t--)
66     {
67         cin >> n;
68         init(n);
69         for (int i = 0; i < n; i++) cin >> s[i];
70         int cnt = 0;
71         for (int i = 0; i < n; i++)
72         {
73             for (int j = i + 1; j < n; j++)
74             {
75                 es[cnt].a = i; es[cnt].b = j; es[cnt].l = edit_dis(s[i], s[j]);
76                 cnt++;
77             }
78         }
79         sort(es, es + cnt, cmp);
80         ll ans = 0; int tot = n;
81         for (int i = 0; i < cnt; i++)
82         {
83             int px = find(es[i].a), py = find(es[i].b);
84             if (px == py) continue;
85             int tmp = uni(es[i].a, es[i].b);
86             num[tmp] = num[px] * num[py] % MOD;
87             if (check(tmp, cnt)) num[tmp] = (num[tmp] + 1) % MOD;
88             tot--;
89             if (tot == 1) ans = num[tmp];
90         }
91         cout << ans << endl;
92     }
93     return 0;
94 }