做冲压件加工有什么好网站,网站建设维保合同,亚马逊雨林探险之旅作文,网站系统建设目标范本OJ题号#xff1a; BZOJ1016 题目大意#xff1a; 给定一个无向带权图#xff0c;求最小生成树的个数。 思路#xff1a; 先跑一遍最小生成树#xff0c;统计相同权值的边出现的个数。 易证不同的最小生成树#xff0c;它们不同的那一部分边的权值实际上是… OJ题号 BZOJ1016 题目大意 给定一个无向带权图求最小生成树的个数。 思路 先跑一遍最小生成树统计相同权值的边出现的个数。 易证不同的最小生成树它们不同的那一部分边的权值实际上是相同的。 所以我们可以暴力枚举相同权值的边统计加入这些边总共能有多少种方法。 根据乘法原理把每种边的方法数乘起来即可。 然后就O(2^n)暴力水过这道题。 实际上用Matrix-Tree可以做到O(n^3)。 1 */2 #includecstdio3 #includecctype4 #includevector5 #includealgorithm6 7 inline int getint() {8 register char ch;9 while(!isdigit(chgetchar()));10 register int xch^0;11 while(isdigit(chgetchar())) x(((x2)x)1)(ch^0);12 return x;13 }14 const int mod31011;15 const int V101;16 17 struct Edge1 {18 int u,v,w;19 bool operator (const Edge1 another) const {20 return wanother.w;21 }22 };23 std::vectorEdge1 e1;24 25 struct Edge {26 int to,w;27 };28 std::vectorEdge e[V];29 inline void add_edge(const int u,const int v,const int w) {30 e[u].push_back((Edge){v,w});31 }32 33 struct DisjointSet {34 int anc[V],cnt;35 int find(const int x) const {36 return xanc[x]?x:find(anc[x]);37 }38 void reset(const int n) {39 cntn;40 for(register int i1;in;i) {41 anc[i]i;42 }43 }44 void Union(const int x,const int y) {45 anc[find(x)]find(y);46 cnt--;47 }48 bool isConnected(const int x,const int y) const {49 return find(x)find(y);50 }51 int stat() const {52 return cnt;53 }54 };55 DisjointSet s;56 57 struct Hash {58 unsigned l,r;59 int v;60 };61 std::vectorHash a;62 63 inline void kruskal() {64 std::sort(e1.begin(),e1.end());65 for(register unsigned i0;ie1.size();i) {66 if(!i) {67 a.push_back((Hash){0,0,0});68 } else if(e1[i].w!e1[i-1].w) {69 a.back().ri-1;70 a.push_back((Hash){i,0,0});71 }72 const int ue1[i].u,ve1[i].v,we1[i].w;73 if(s.isConnected(u,v)) continue;74 s.Union(u,v);75 add_edge(u,v,w);76 add_edge(v,u,w);77 a.back().v;78 }79 a.back().re1.size()-1;80 }81 82 int tmp;83 void dfs(const int in,const unsigned x,const int d) {84 if(xa[in].r) {85 if(da[in].v) tmp;86 return;87 }88 const int ue1[x].u,ve1[x].v;89 const int ps.find(u),qs.find(v);90 if(p!q) {91 s.anc[p]q;92 dfs(in,x1,d1);93 s.anc[p]p;94 s.anc[q]q;95 }96 dfs(in,x1,d);97 }98 99 int main() {
100 int ngetint();
101 for(register int mgetint();m;m--) {
102 const int ugetint(),vgetint(),wgetint();
103 e1.push_back((Edge1){u,v,w});
104 }
105 s.reset(n);
106 kruskal();
107 if(s.stat()!1) {
108 puts(0);
109 return 0;
110 }
111 s.reset(n);
112 int ans1;
113 for(register unsigned i0;ia.size();i) {
114 tmp0;
115 dfs(i,a[i].l,0);
116 ans(ans*tmp)%mod;
117 for(register unsigned ja[i].l;ja[i].r;j) {
118 const int ue1[j].u,ve1[j].v;
119 if(s.isConnected(u,v)) continue;
120 s.Union(u,v);
121 }
122 }
123 printf(%d\n,ans);
124 return 0;
125 } 转载于:https://www.cnblogs.com/skylee03/p/7575427.html
