社区讨论

求帮忙交cf题

灌水区参与者 4已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@m5z8wa3v
此快照首次捕获于
2025/01/16 19:26
去年
此快照最后确认于
2025/01/16 22:53
去年
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int n,t,cnt,vis[262144];
double a[19][19],dp[262144];
queue<int>q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	dp[(1<<n)-1]=1;
	q.push((1<<n)-1);
	while(q.size()){
		t=q.front();
		q.pop();
		cnt=0;
		for(int i=1,j=1;i<=n;i++,j<<=1){
			if(t&j){
				cnt++;
			}
		}
		cnt=cnt*(cnt-1);
		for(int i=1,j=1;i<=n;i++,j<<=1){
			if(t&j){
				for(int k=1,l=1;k<=n;k++,l<<=1){
					if(t&l&&j!=l){
						dp[t^j]+=dp[t]*a[k][i]/cnt;
						dp[t^l]+=dp[t]*a[i][k]/cnt;
						if(!vis[t^j]){
							vis[t^j]=1;
							q.push(t^j);
						}
						if(!vis[t^l]){
							vis[t^l]=1;
							q.push(t^l);
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%.6lf ",dp[1<<i-1]);
	}
}

回复

5 条回复,欢迎继续交流。

正在加载回复...