自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:55:46，当前版本为作者最后更新于2018-09-13 19:33:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道神奇的Matrix-Tree定理题……

前置芝士:矩阵树定理

蛤？做cp题不会矩阵树定理?如果不会的话请自行度娘

本题题解

先来简述一下题意，给你一张网格图，每个格子上有一个箭头，还有一些格子是不定向的，现在希望给这些格子定向，使得这张网格图当中不存在环，求合法的定向方案数

我们考虑将这张网格图转化成一个真正的图……

那么建图方法依然很简单，原来网格图上的点还是原来的点，然后如果这个点上写着L的话就把这个点和它左边的点连有向边，写着R的话就把这个点和它右边的点连有向边,写着U的话就把这个点和它上边的点连有向边，写着D的话就把这个点和它下边的点连有向边

然后新建一个虚点表示"外面的区域",也就是如果在刚才的建图方式当中上/下/左右边的点不存在的话我们就将这个点和这个表示外面的点连有向边

那么我们发现如此这般转化后的新图满足两个性质

1.如果这张图合法的话图中是没有环的

2.如果这张图合法的话，图中的每一个点都存在一条到达表示外部的虚点的有向路径

(其实上边两句都是废话)

然后我们发现这个图有一个更加重要的性质是这个图只有$nm$条边却有$nm+1$个点，另外所有的点(除了虚点例外)的出度都为1

这些性质指向了一个共同的结论，就是一张合法的图转化之后必然是一张有向的树形图，并且以我们新建的虚点为根

那么此时的问题开始渐渐变得明朗起来了，我们现在的目标就是对树形图计数，这个问题是有明确的$O(n^3)$算法的，也就是通过矩阵树定理来求解

但是似乎对于这道题，如果我们将每一个方向未知的点向四周连4条有向边，然后其余点正常连边，最后跑一趟矩阵树定理进行树形图计数的话，我们会得到一个优秀的$O(n^3m^3)$的暴力

这样的复杂度实在是不优秀，所以我们需要想一些更加机智的算法

突然发现方向未定的点最多只有300个那么我们可以考虑是不是可以把这张图缩一缩点，只保留关于未知点的信息呢？

我们发现一个性质就是，我们一旦走到了某一个点i，j之后接下来的走法完全是完全一样的，而和我怎么走到这个i，j无关

因此这张图上的一条路径是否存在仅仅和这条路径上的不定向点的决策是否正确有关

此时我们可以暴力模拟/dfs找出一个不定向点在定向为/上/下/左/右之后第一个到达的未定向点(或者是那个表示外界的虚点)，然后将这个点和这个点一个到达的点连一条边(这样的话总计一个点会连4条边)

那么我们对这样建出的图跑矩阵树定理得出的生成树方案树和原图中的生成树方案树将会是相等的，因为我们这么做相当于把原图中已经是树的部分去掉了而直接在不确定的点之间连边

此时我们的复杂度是$O(T((n+m)nm+k^3))$已经可以通过本题了

不过如果你常数大一点的话可能就T飞了……

想要优化复杂度的话可以把刚才的爆搜改成记忆化爆搜，此时的复杂度就变成了$O(T(nm+k^3))$就可以轻松的通过本题辣~

tips:给有向图做树形图统计的话，对于这道题的话我们的基尔霍夫矩阵应该是入度矩阵-临接矩阵，而求行列式时删掉的一行一列也不再是随便删而是删去树形图的根(本题中就是我们建的那个虚点)

tips:记得在这张图中有环的时候输出0

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=310;typedef long long ll;const ll mod=1e9+7;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
int n;int m;int tr[N][N];int ctt;ll kr[N][N];char mde[N][N];int id[N][N];int T;
int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
inline ll det()//高斯削元求行列式 
{
	ll res=1;int t=0;for(int i=1;i<ctt;i++)for(int j=1;j<ctt;j++)(kr[i][j]+=mod)%=mod;
	for(int i=1;i<ctt;i++)
	{
		if(kr[i][i]==0)for(int j=i+1;j<ctt;j++)
			if(kr[j][i]!=0){for(int k=i;k<ctt;k++)swap(kr[j][k],kr[i][k]);t^=1;break;}
		if(kr[i][i]==0)return 0;(res*=kr[i][i])%=mod;ll inv=po(kr[i][i],mod-2);
		for(int j=i;j<ctt;j++)(kr[i][j]*=inv)%=mod;
		for(int j=1;j<ctt;j++)
			if(i!=j)for(int k=ctt-1;k>=i;k--)(kr[j][k]+=mod-kr[i][k]*kr[j][i]%mod)%=mod;
	}return t?(mod-res)%mod:res;
}
inline void add(int u,int V){kr[u][u]++;kr[u][V]--;}
inline int dfs(int px,int py)//记忆化搜索出从每个点出发后到达的第一个未定向点/虚点 
{
	if(px<1||px>n||py<1||py>m)return ctt;if(tr[px][py]!=0)return tr[px][py];
	switch(mde[px][py])
	{
		case 'L':{tr[px][py]=dfs(px+dx[0],py+dy[0]);break;}
		case 'R':{tr[px][py]=dfs(px+dx[1],py+dy[1]);break;}
		case 'U':{tr[px][py]=dfs(px+dx[2],py+dy[2]);break;}
		case 'D':{tr[px][py]=dfs(px+dx[3],py+dy[3]);break;}
	}return tr[px][py];
}
inline bool dfs(int px,int py,int col)//dfs判环 
{
	if(px<1||px>n||py<1||py>m)return true;
	if(id[px][py]==col)return false;if(id[px][py]!=0)return true;id[px][py]=col;
	switch(mde[px][py])
	{
		case 'L':{return dfs(px+dx[0],py+dy[0],col);break;}
		case 'R':{return dfs(px+dx[1],py+dy[1],col);break;}
		case 'U':{return dfs(px+dx[2],py+dy[2],col);break;}
		case 'D':{return dfs(px+dx[3],py+dy[3],col);break;}
	}return true;
}
inline void solve()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s",mde[i]+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mde[i][j]=='.')tr[i][j]=++ctt;++ctt;
	for(int i=1,c=0;i<=n;i++)
		for(int j=1;j<=m;j++)if(id[i][j]==0&&dfs(i,j,++c)==false){printf("0\n");return;}
	for(int i=1;i<=n;i++)//建图 
		for(int j=1;j<=m;j++)if(mde[i][j]=='.')for(int k=0;k<4;k++)add(tr[i][j],dfs(i+dx[k],j+dy[k]));
	printf("%lld\n",det());//跑矩阵树定理 
}
inline void clear()
{
	for(int i=1;i<=ctt;i++)for(int j=1;j<=ctt;j++)kr[i][j]=0;ctt=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)tr[i][j]=0;
}
int main(){scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;}//拜拜程序~