[BZOJ4011][HNOI2015]落忆枫音：拓扑排序+容斥原理

分析

又是一个有故事的题目背景。作为玩过原作的人，看题目背景都快看哭了ToT。强烈安利本境系列，话说SP-time的新作要咕到什么时候啊。

好像扯远了嘛不管了。

一句话题意就是求一个DAG再加上一条有向边所构成的有向图的以\(1\)为根的外向树形图的个数。

考虑一个DAG的情况，答案显然是：

\[\prod_{i=2}^{n}in[i]
\]

其中\(in[i]\)表示结点\(i\)的入度，这个式子的意思就是给每个非根结点选一条入边。由于是DAG所以这样构造出来的一定是一个外向树形图。

加入一条边后，图上可能会出现环，如果有一些结点选择的入边正好构成一个环的话，那么这样构造出的图是不合法的。

而每个这样的环会让答案减去\(\frac{\prod_{i=2}^{n}in[i]}{\prod_{i在环上}in[i]}\)。

设新加入的边为\(s \to t\)，考虑到每个环都是由原图中\(t\)到\(s\)的一条路径加上\(s \to t\)这条新加入的边构成的，所以我们就可以通过拓扑排序统计那个东西了。

时间复杂度可以做到\(O(n)\)。（不过博主因为快速幂算逆元多了个\(\log\)）

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=100005;

const int MAXM=200005;

const LL MOD=1e9+7;

int n,m,s,t,ecnt,head[MAXN];

int out[MAXN],in[MAXN];

LL f[MAXN];

std::queue<int> q;

struct Edge{

	int to,nxt;

}e[MAXM];

inline void add_edge(int bg,int ed){

	++ecnt;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

inline LL qpow(LL x,LL y){

	LL ret=1,tt=x%MOD;

	while(y){

		if(y&1) ret=ret*tt%MOD;

		tt=tt*tt%MOD;

		y>>=1;

	}

	return ret;

}

LL topo(){

	while(!q.empty()) q.pop();

	rin(i,1,n)

		if(!out[i])

			q.push(i);

	f[s]=1;

	while(!q.empty()){

		int x=q.front();q.pop();

		f[x]=f[x]*qpow(in[x],MOD-2)%MOD;

		trav(i,x){

			int ver=e[i].to;

			--out[ver];

			if(!out[ver]) q.push(ver);

			f[ver]=(f[ver]+f[x])%MOD;

		}

		if(x==t) return f[x];

	}

}

int main(){

	n=read(),m=read(),s=read(),t=read();

	++in[t];

	rin(i,1,m){

		int u=read(),v=read();

		++out[u],++in[v];

		add_edge(v,u);

	}

	LL ans=1;

	rin(i,2,n) ans=ans*in[i]%MOD;

	if(t==1){

		printf("%lld\n",ans);

		return 0;

	}

	ans=(ans-topo()*ans%MOD+MOD)%MOD;

	printf("%lld\n",ans);

	return 0;

}

巴特西

[BZOJ4011][HNOI2015]落忆枫音：拓扑排序+容斥原理

分析

代码

最新文章

热门文章