首页 > 代码库 > BZOJ 1016 最小生成树计数
BZOJ 1016 最小生成树计数
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
8
HINT
Source
这题要猜一个结论——长为i的边个数是一定的以及前i小的边他们构成的并查集是一定的，这样就可以 2^n dfs了（相同长度的边<=10）。
1 #include<algorithm> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 7 #define maxn (110) 8 #define maxm (1010) 9 #define rhl (31011)10 11 int father[maxn],save[maxn],bac[maxm],road[maxm];12 int n,m,tot,ans,sum;13 struct E{ int u,v,w; }edge[maxm];14 15 inline void init() {for (int i = 1;i <= n;++i) father[i] = i;}16 17 inline int find(int a) {if (father[a] != a) father[a] = find(father[a]); return father[a];} 18 19 inline bool cmp(E a,E b){ return a.w < b.w; }20 21 inline void mst()22 {23 sort(edge+1,edge+m+1,cmp); init();24 int have = 0,r1,r2,pos;25 for (int i = 1;i <= m;++i)26 {27 r1 = find(edge[i].u),r2 = find(edge[i].v);28 if (r1 != r2)29 {30 father[r1] = r2; ++have;31 pos = lower_bound(bac+1,bac+tot+1,edge[i].w)-bac;32 ++road[pos];33 }34 if (have == n - 1) break;35 }36 if (have < n - 1) printf("0"),exit(0);37 }38 39 inline void dfs(int a,int r,int pos,int cho)40 {41 if (road[pos] == cho)42 {43 ++sum;44 if (sum == 1) memcpy(save,father,sizeof(save));45 return;46 }47 if (a > r) return;48 if (cho+r-a+1<road[pos]) return;49 int temp[maxn];50 dfs(a+1,r,pos,cho);51 memcpy(temp,father,sizeof(temp));52 int r1 = find(edge[a].u),r2 = find(edge[a].v);53 if (r1 != r2) father[r1] = r2,dfs(a+1,r,pos,cho+1);54 memcpy(father,temp,sizeof(temp));55 }56 57 int main()58 {59 freopen("1016.in","r",stdin);60 freopen("1016.out","w",stdout);61 scanf("%d %d",&n,&m);62 for (int i = 1;i <= m;++i)63 {64 int a,b,c;65 scanf("%d %d %d",&a,&b,&c);66 edge[i] = (E) {a,b,c};67 bac[i] = c;68 }69 sort(bac+1,bac+m+1);70 tot = unique(bac+1,bac+m+1)-bac-1;71 mst();72 init(); ans = 1;73 for (int i = 1;i <= m;)74 {75 int j = i;76 while (j < m && edge[j+1].w == edge[i].w) ++j;77 sum = 0;78 dfs(i,j,lower_bound(bac+1,bac+tot,edge[i].w)-bac,0);79 (ans *= sum)%=rhl;80 memcpy(father,save,sizeof(save));81 i = j+1;82 }83 printf("%d",ans);84 fclose(stdin); fclose(stdout);85 return 0;86 }
BZOJ 1016 最小生成树计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。