NOI批量评测 - 记录详情

foo.cc: In function 'long long int ss2(long long int)':
foo.cc:18:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   18 |         if(S==(1<<n+1)-2) return 0;
      |                   ~^~
Expand

#	状态分数	耗时	内存占用

#1	Accepted 4	153ms	408 KiB
#2	Accepted 4	158ms	436 KiB
#3	Accepted 4	155ms	440 KiB
#4	Time Exceeded 0	≥4101ms	≥404 KiB
#5	Time Exceeded 0	≥4100ms	≥404 KiB
#6	Time Exceeded 0	≥4101ms	≥404 KiB
#7	Time Exceeded 0	≥4100ms	≥404 KiB
#8	Time Exceeded 0	≥4101ms	≥404 KiB
#9	Time Exceeded 0	≥4100ms	≥408 KiB
#10	Time Exceeded 0	≥4100ms	≥404 KiB
#11	Time Exceeded 0	≥4100ms	≥404 KiB
#12	Time Exceeded 0	≥4001ms	≥404 KiB
#13	Time Exceeded 0	≥4100ms	≥404 KiB
#14	Time Exceeded 0	≥4100ms	≥404 KiB
#15	Time Exceeded 0	≥4101ms	≥404 KiB
#16	Time Exceeded 0	≥4100ms	≥404 KiB
#17	Time Exceeded 0	≥4100ms	≥404 KiB
#18	Time Exceeded 0	≥4101ms	≥404 KiB
#19	Time Exceeded 0	≥4101ms	≥404 KiB
#20	Time Exceeded 0	≥4001ms	≥336 KiB
#21	Time Exceeded 0	≥4100ms	≥404 KiB
#22	Time Exceeded 0	≥4101ms	≥408 KiB
#23	Time Exceeded 0	≥4100ms	≥404 KiB
#24	Time Exceeded 0	≥4100ms	≥404 KiB
#25	Time Exceeded 0	≥4001ms	≥404 KiB

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=20,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int qpow(int x,int p){
	int y=1;
	while(p){
		if(p&1) y=y*x%mod;
		x=x*x%mod,p>>=1;
	}
	return y;
}
int c,T,n,m,mp[N][N],ne_ans,tmp_mp[N][N],ans1,ans2;
bool bjt[N];
int f[N];

int ss2(int S){
	if(S==(1<<n+1)-2) return 0;
	int ans=INF;
	for(int i=1;i<=n;i++) if((~S)>>i&1){
		int tmp=INF;
		for(int j=1;j<=n;j++) if(S>>j&1) tmp=min(tmp,tmp_mp[j][i]);
		ans=min(ans,tmp+ss2(S|1<<i));
//		printf("#%lld %lld\n",tmp,ans);
	}
	return ans;
}
void ss(int x,int y){
//	printf("#%d %d\n",x,y);
	if(x==n+1){
		ans2++; 
		for(int i=1;i<=n;i++) if(ss2(1<<i)==ne_ans){
			ans1++;
			break; 
		}
		return;
	}
	tmp_mp[x][y]=INF;
	if(mp[x][y]!=INF) tmp_mp[x][y]=mp[x][y],y==n?ss(x+1,1):ss(x,y+1),tmp_mp[x][y]=INF;
	y==n?ss(x+1,1):ss(x,y+1); 
}
void solve(){
	memset(mp,0x3f,sizeof(mp));
	memset(f,0x3f,sizeof(f));
	memset(bjt,0,sizeof(bjt));
	memset(tmp_mp,0x3f,sizeof(tmp_mp));
	ne_ans=ans1=ans2=0;
	
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,mp[u][v]=mp[v][u]=w;
	
	f[1]=0;
	for(int i=1;i<=n;i++){
		int gt=0;
		for(int j=1;j<=n;j++) if(!bjt[j]&&f[j]<f[gt]) gt=j;
		ne_ans+=f[gt],bjt[gt]=1;
		for(int j=1;j<=n;j++) f[j]=min(f[j],mp[gt][j]);
	}
	ss(1,1);
//	printf("#%lld %lld %lld\n",ne_ans,ans1,ans2);
	cout<<(ans1*qpow(ans2,mod-2)%mod+mod)%mod<<"\n";
}
signed main(){
	freopen("years.in","r",stdin);
	freopen("years.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0);
	cin>>c>>T;
	while(T--) solve();
	return 0;
}
/*
0 1
2 1
1 2 1

这个逻辑有点绕
假如我们只计算根是1的对象，
那么我们可以通过钦定一个存在生成树的图的代表生成树的方式，将一个图映射到一个生成树，
然后，虽然我们是仍要计数图，但是我们的核心已经转到树了，
具体地，我们设f[S][x]表示图中目前已加入树的节点为S,最后一个加入的为x的概率，
然后我们要考虑下一个节点可能的情况，
自然，我们要从最小的未被考虑的开始考虑，
如果其<S中最大的节点（设为y）,
那么说明其已经被S中除x以外的所有节点考虑过了（而且都不可以，而且概率也已经累加了），
那么只有x需要考虑，
否则，所有的节点都要对它来一轮，
然后，最后的概率需要累加到下一个决策对象上

对于每个存在生成树的图，其中每一个生成树都是和一个以1为根的生成树轮廓重合的（废话）
对于一个图， 

上面那个问题其实可以用矩阵树定理简单解决，
但是下面这个还是困难 
*/ 
/*
如何描摹？

这会和朱刘算法有关吗？

显然，无论产生了什么图，结果<=原图

考虑逐步产生最小树形图，
但是这东西并不好描摹

我们考虑分拆问题，
设f(x)表示值相等，并且x为最小根时的概率，
然而我仍然对最小外向生成树没有什么概念，

可以建一个虚拟根方便考虑，
不对，不行

借助prim的思想，我们可以发现，
并不对，有向图不能这么考虑

不行，在描摹最小生成外向树这一点上仍然存在这较大的困难，
我目前还没有想到很好的描摹方法

特殊性质C相当于求仍然存在外向生成树的概率，
因为数据范围小，所以我们整体可以容斥，
容斥之后问题就变成了若干个对象要同时可为最小生成树的根，
这意味着这若干个对象要处于一个强连通分量中，
但是这并不容易考虑，

对于一个图，我们

算了，先把最朴素的分拿了吧

对于单一对象作为起点，
我们可以通过规定生成树的生成方式以及一个图的生成树钦定方式
（不是很显然）我们有一种对于一个图唯一生成一个对应生成树的方式，
就是每次连接当前连通块能连接的最小的点，每次通过已有的能连的最小的点去连，
基于这个方法，我们就可以将边带权考虑（可以定义一个生成树的权值为边权之和），
不过在这个过程中，我们发现概率似乎不是完全独立的，
所以应该还需要更细致地考虑

主要问题在于原问题仍然难以解决
容斥之后的问题也仍然不好做
钦定也存在一点问题

每个生成树是不是会被算固定的次数呢？
也许是，但这对于我们的整个问题……
？

这道题啃的时间太久了，
我们需要先去解决第一道题 
*/

递交者: SC-135
题目: NOISX2025GFE NOISX2025GFE
比赛: 【官方数据 SC】联合省选 2025 批量测试
语言: C++14(O2)
代码长度: 2.5 KiB
递交时间: 2025-3-6 14:04:02
评测时间: 2025-3-6 17:40:17

分数: 12
总耗时: ≥90375ms
峰值时间: ≥4101ms
峰值内存: ≥440 KiB

12 Time Exceeded

代码

信息

还没有账户？

登录