基于kruscal的贪心 可以有如下推论：两个不同的最小生成树所用的的相同边权的边的数量相同。
可以做这样的理解：当进行到选第K大的边时，联通快数是一定的所以的、一定需要K- 1个该权值边 （不知道对不对 欢迎TuneProverbs指正）
SB没想好怎么存水体写半天。。。。。。。
我是SB 1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N = 1500;typedef long long LL; 8 vector v[N]; 9 vector ::iterator it, ptr; 10 int n, m, p[N], cnt[N], cc, r[N]; 11 LL ans; 12 bool vis[N], cantvisit[N], noans; 13 struct Q { 14 int x, y, w, num; 15 inline bool operator < (const Q & a) const { 16 return w < a.w; 17 } 18 }e[N]; 19 inline int F (int x) { return p[x] == x ? x : p[x] = F (p[x]); } 20 void ksc () 21 { 22 for (int i = 1; i <= n; i ++) 23 p[i] = i; 24 sort (e + 1, e + 1 + m); 25 for (int i = 1; i <= m; i ++) 26 if (F (e[i].x) != F (e[i].y)) 27 { 28 p[F (e[i].x)] = F (e[i].y); 29 ans += e[i].w; 30 int j (0); 31 for (int j = 1; j <= cc; j ++) 32 if (r[j] == e[i].w) 33 cnt[j] ++; 34 } 35 for (int i = 2; i <= n; i ++) 36 if (F (i) != F (i - 1)) 37 noans = true; 38 //for (int i = 1; i <= 5; i ++) 39 // printf ("%d\n", cnt[i]); 40 //printf ("%d\n", ans); 41 } 42 bool ck () 43 { 44 for (int i = 1; i <= n; i ++) 45 p[i] = i; 46 sort (e + 1, e + 1 + m); 47 LL z (0); 48 for (int i = 1; i <= m; i ++) 49 { 50 if (cantvisit[e[i].num]) continue; 51 if (F (e[i].x) != F (e[i].y)) 52 { 53 p[F (e[i].x)] = F (e[i].y); 54 z += e[i].w; 55 } 56 } 57 //printf ("%d\n", z); 58 return z == ans; 59 } 60 inline int calc (int j) 61 { 62 int z (0); 63 for (; j; j -= j & -j) z ++; 64 return z; 65 } 66 int main () 67 { 68 scanf ("%d%d", &n, &m); 69 for (int i = 1; i <= m; i ++) 70 scanf ("%d%d%d", &e[i].x, &e[i].y, &e[i].w), e[i].num = i; 71 for (int i = 1; i <= m; i ++) 72 { 73 if (vis[i]) continue; 74 cc ++; 75 r[cc] = e[i].w; 76 v[cc].push_back (i); 77 for (int j = i + 1; j <= m; j ++) 78 if (e[j].w == e[i].w) 79 { 80 vis[j] = true; 81 v[cc].push_back (j); 82 } 83 } 84 ksc (); 85 if (noans == true) 86 { 87 puts ("0"); 88 return 0; 89 } 90 int z (1); 91 for (int j = 1; j <= cc; j ++) 92 { 93 int tmp (0); 94 //printf ("*%d\n", v[j].size ()); 95 for (int i = 0; i < (1 << v[j].size ()); i ++) 96 { 97 if (calc (i) == cnt[j]) 98 { 99 int k (0);100 for (ptr = v[j].begin (); ptr != v[j].end (); ptr ++, k ++)101 if ((i >> k) & 1)102 ;103 else104 cantvisit[*ptr] = true;105 //for (int i = 1; i <= m; i ++)106 // printf ("%d", cantvisit[i]);puts ("");107 int t (0);108 if (t = ck ())109 tmp ++;110 memset (cantvisit, 0, sizeof cantvisit);111 }112 }113 //printf ("%d\n", tmp);114 if (tmp != 0)115 z = ((long long)z * tmp) % 31011;116 }117 printf ("%d\n", z);118 return 0;119 }