A40842. 广场舞
填空题
困难
知识点
题目描述
广场舞
题目描述
给定一个 n*m 的格点图，包含 n 行 m 列共 n*m 个顶点，相邻的顶点之间有一条边。
【图1.png】给出了一个3*4的格点图的例子。
如果在图中删除部分顶点和其相邻的边，如上图删除第2行第3列和第3行第1列的顶点后，如【图2.png】所示。
图的生成树指包含图中的所有顶点和其中的一部分边，使得任意两个顶点之间都有由边构成的唯一路径。如果两个生成树包含有不同的边即被认为不同，则上图中共有31种不同的生成树，其中a边不选有10种，a边选有21种。
给出格点图中保留的顶点的信息，请计算该图一共有多少种不同的生成树。
输入格式
输入的第一行包含两个整数n, m，用空格分隔，表示格点图的行数和列数。
接下来n行，每行m个字母（中间没有分隔字符），每个字母必然是大写E或大写N，E表示对应的顶点存在，N表示对应的顶点不存在。保证存在至少一个顶点。
输出格式
输出一行，包含一个整数，表示生成树的个数。答案可能很大，你只需要计算答案除以1000000007的余数即可。
样例输入
3 4
EEEE
EENE
NEEE
样例输出
31
参考答案
#include <bits/stdc++.h>
#define mod 1000000007
typedef long long ll;
using namespace std;
int n, m, cnt, ans, kk;
char s[8][100005];
int vis[700000];
int flag[700000];
int fa[700000];
struct E {
int u, v;
};
E e[1400000];
//路径压缩并查集
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
//x:边的序号, pcnt:已连接的点的个数， ecnt:已选择的边数
void dfs(int x,int pcnt,int ecnt) {
//遍历完所有的边
if(x == cnt) {
//点的个数与边的个数符合生成树特点
if(pcnt == n * m - kk && ecnt == n * m - 1 - kk) {
for(int i = 0; i <= n * m; i++) {
fa[i] = i;
}
//判断环
for(int i = 0; i < cnt; i++) {
if(flag[i] == 1) {
int a = find(e[i].u);
int b = find(e[i].v);
if(a == b) {
return ;//如果构成环路
}
fa[a]=b;
}
}
ans++;
}
return ;
}
int u = e[x].u, v = e[x].v;
int k1 = vis[u], k2 = vis[v];
vis[u] = 1;
vis[v] = 1;
flag[x] = 1;
//选择x这条边
//pcnt+2-k1-k2表示要去除以及选择了的点
dfs(x + 1, pcnt + 2 - k1 - k2, ecnt + 1);
vis[u] = k1;//注意这里的回溯
vis[v] = k2;
flag[x] = 0;
//不选择x这条边
dfs(x + 1, pcnt, ecnt);
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> s[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < m; j++) {
//上下方向的边
if(s[i][j] == 'E' && s[i + 1][j] == 'E') {
//设置边的端点的序号
e[cnt].u = (i - 1) * m + j + 1;
e[cnt++].v = i * m + j + 1;
}
//左右方向的边
if(s[i][j] == 'E' && s[i][j + 1] == 'E') {
e[cnt].u = (i - 1) * m + j + 1;
e[cnt++].v = (i - 1) * m + j + 2;
}
if(s[i][j] == 'N') {
kk++; //统计为空的点
}
}
}
dfs(0, 0, 0);
cout << ans;
return 0;
}
上一题
下一题