列表

详情

NC17667. Enumeration not optimization

描述

Niuniu is (p)reviewing NOIP 2017 problems.
Maybe you have heard NOIP 2017 Day 2 Problem 2 Treasure.
You can find the problem at https://www.nowcoder.com/acm/contest/154/1002.
He found that the official data is very weak. Many contestants accepted this problem with search solutions or wrong solutions.

Let's consider the enumeration version of this problem.
We want to find the sum of weight of all rooted spanning tree.
The weight of a rooted spanning tree is defined as follows.

Enumerate all edges in the tree.
The contribution of an edge is its weight times its depth in the rooted tree.

The depth of a vertex is the number of edges from the root to the vertex.

As the answer might be very large, you only need to output the answer mod 1000000007.

输入描述

The first line contains two integers n, m, which are the number of vertices and the number of edges.
In the following m lines, each line contains three integers x, y, z, which means there is an edge between x and y, whose weight is z.

1 <= n <= 12
1 <= m <= 1000
1 <= x <= n
1 <= y <= n
1 <= z <= 5000

输出描述

You should ouput one line, which contains the answer.

示例1

输入: 

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

输出: 

303

示例2

输入: 

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

输出: 

336

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 154ms, 内存消耗: 1272K, 提交时间: 2022-05-01 14:00:03 

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long f[13][1<<13],g[13][1<<13];
long long h[1<<13],x[3000],y[3000],n,m,c[13][13],w[3000],ans=0;
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%lld%lld%lld",&x[i],&y[i],&w[i]);
		--x[i];
		--y[i];
		++c[x[i]][y[i]];
		++c[y[i]][x[i]];
	}
	for(int i=1;i<1<<n;++i)
	{
		for(int j=i;j;j>>=1)
		h[i]+=j&1;
		for(int j=0;j<n;++j)
		if(i>>j&1)
		{
			int u=i^(1<<j),v=u&(-u);
			if(!u)
			{
				f[j][i]=g[j][i]=1;
				break;
			}
			for(int k=u;k;k=(k-1)&u)
			if(k&v)
			{
				for(int l=0;l<n;++l)
				if((k>>l)&1)
				{
					int subsum=(f[l][k]+h[k]*g[l][k])%mod*g[j][i^k]%mod;
					f[j][i]=(f[j][i]+(f[j][i^k]*g[l][k]%mod+subsum)%mod*c[j][l])%mod;
					g[j][i]=(g[j][i]+g[j][i^k]*g[l][k]%mod*c[j][l]%mod)%mod;
				}
			}
		}
	}
	int s=(1<<n)-1;
	for(int i=1;i<=m;++i)
	for(int j=1<<x[i];j<1<<n;j=(j+1)|(1<<x[i]))
	ans=(ans+w[i]*(f[x[i]][j]*g[y[i]][s^j]%mod+f[y[i]][s^j]*g[x[i]][j]%mod))%mod;
	printf("%lld\n",ans);
	return 0; 
}

上一题

© 2024 nowcoder.com