渗透实验
给定黑格数量
黑格随机分布,生成一个矩阵,黑格子表示不通,白格表示通
循环很多次,求在当前黑格数量下,从上到下矩阵通的概率
Eg
1 0 1 1 0 1
1 0 0 0 1 1
0 1 1 0 1 0
1 0 1 0 1 0
[0 1] - [1 1] - [1 2] - [1 3] - [2 3] - [3 3] -> 通
思路
在首行前和末行后添加一个起始点和终止点
从起始点开始,若有白格与之相连,则将其加入一个集合(并查集操作)
遍历白格,将相连的白格放入一个集合
…
最后看终止点和起始点是否在一个集合
#include <iostream>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std;
const int N = 1000;
class unionFind{
public:
unionFind(int size);
~unionFind();
void union_node(int p, int q);
int find(int p);
bool connected(int p, int q);
int count();
private:
int num;
int *id;
int *rootSize;
};
unionFind::unionFind(int size){
num = size;
id = new int[size];
rootSize = new int[size];
for (int i = 0; i < size; i ++){
id[i] = i;
}
for (int i = 0; i < size; i ++){
rootSize[i] = 1;
}
}
unionFind::~unionFind(){
delete[] id;
num = 0;
}
int unionFind::count(){
return num;
}
bool unionFind::connected(int p, int q){
return find(p) == find(q);
}
int unionFind::find(int p){
if (p != id[p]) p = find(id[p]);
return p;
}
void unionFind::union_node(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if (qRoot == pRoot) return;
if (rootSize[pRoot] < rootSize[qRoot]){
id[pRoot] = qRoot;
rootSize[qRoot] += rootSize[pRoot];
}
else{
id[qRoot] = pRoot;
rootSize[pRoot] += rootSize[qRoot];
}
num --;
}
int net[N][N];
bool st[N][N];
double pass, times;
double fi;
//遍历上下左右四个格子
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int main(){
cin >> times;
cin >> fi;
int cnt = 0;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++){
net[i][j] = ++ cnt;
}
void srand(unsigned int seed);
for (int t = 0; t < times; t ++){
memset(st, false, sizeof st);
for (int i = 0; i < fi * N * N; ){
int x = rand() % N;
int y = rand() % N;
//cout << x << ' ' << y << endl;
if (!st[x][y]) i ++;
st[x][y] = true;
}
//创建并查集
unionFind uF(N * N + 10);
int start = N * N + 1;
int end = N * N + 2;
//在最上方和最下方创建起始点和终止点
//通过判断起始点和终止点是否连通来判断是否渗透
for (int i = 0; i < N; i ++){
uF.union_node(start, net[0][i]);
uF.union_node(end, net[N - 1][i]);
}
//创建连通片
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++){
//如果当前块为通
if (st[i][j]){
//遍历四个方向的方块
for (int k = 0; k < 4; k ++){
int x = i + dx[k], y = j + dy[k];
//如果方块合法,且为通
if (x >= 0 && x < N && y >= 0 && y < N && st[x][y]){
//如果两方块没有连通,则连通两方块
if (!uF.connected(net[x][y], net[i][j])){
uF.union_node(net[x][y], net[i][j]);
}
}
}
}
}
//如果首尾节点连通
if (uF.connected(start, end)){
pass ++;
}
}
cout << pass / times << endl;
return 0;
}