http://www.lydsy.com/JudgeOnline/problem.php?id=4011
记新加入的边的起点为$x$，终点为$y$
首先，我们先考虑新加入的边没有构成环的情况,即在原图中$x$能到$y$：
这时还是一个有向无环图。
根据朱刘算法的推论，记$indegree[i]$表示点$i$的入度，那么答案就是$sumlimits_{i=1}^{n}indegree[i]$
现在考虑新加入的边构成了环的情况，即在原图中$y$能到$x$：
我们发现，其实$sumlimits_{i=1}^{n}indegree[i]$算多了非法情况。
我们统计非法情况的个数。
我们发现在非法情况中一定包含新加入的边和一条原图$y$到$x$的路径组成的简单环；对于不在这个简单环上每个点$i$，任选一条以点$i$为终点的有向边，有$degree[i]$个选择。
所以非法情况的个数是：
$sumlimits_{S是y到x的任意一条路径}sumlimits_{j otin S}indegree[j]$
$=sumlimits_{S是y到x的任意一条路径}frac{sumlimits_{j=1}^{n}indegree[j]}{sumlimits_{jin S}indegree[j]}$
用DP。
记$f[i]=sumlimits_{S是y到i的任意一条路径}frac{sumlimits_{j=1}^{n}indegree[j]}{sumlimits_{jin S}indegree[j]}$
易知$f[y]=frac{sumlimits_{j=1}^{n}indegree[j]}{indegree[y]}$
根据拓扑序DP。
如果有一条$u$到$v$边，那么$f[v]+=frac{f[u]}{indegree[v]}$
然后输出$sumlimits_{i=1}^{n}indegree[i]-f[x]$即可。
注意$y=1$的特殊情况。
这题的巧妙之处是我们发现合法情况非常难统计，但是我们我们知道合法情况和非法情况的和，并且非法情况比较容易统计，运用了补集的思想。
#include<cstdio> #include<cstdlib> #include<iostream> #include<fstream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<utility> #include<set> #include<bitset> #include<vector> #include<functional> #include<deque> #include<cctype> #include<climits> #include<complex> //#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> PII; typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a)) #define mmcy(a,b) memcpy(a,b,sizeof(a)) #define fill(a,l,r,v) fill(a+l,a+r+1,v) #define re(i,a,b) for(i=(a);i<=(b);i++) #define red(i,a,b) for(i=(a);i>=(b);i--) #define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++) #define fi first #define se second #define m_p(a,b) make_pair(a,b) #define p_b(a) push_back(a) #define SF scanf #define PF printf #define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;} template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;} template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} inline int sgn(DB x){if(abs(x)<1e-9)return 0;return(x>0)?1:-1;} const DB Pi=acos(-1.0); int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } const int maxn=100000; const int maxm=200000; const LL Mod=1000000007; int n,m,x,y; int now,first[maxn+100]; struct Tedge{int v,next;}edge[maxm+100]; LL degree[maxn+100],_degree[maxn+100]; LL f[maxn+100],ans; void addedge(int u,int v){now++;edge[now].v=v;edge[now].next=first[u];first[u]=now;} LL power(LL a,LL k){LL x=1;while(k){if(k&1)x=x*a%Mod;k>>=1;a=a*a%Mod;}return x;} queue<int>Q; int main() { freopen("bzoj4011.in","r",stdin); freopen("bzoj4011.out","w",stdout); int i; n=gint();m=gint();x=gint();y=gint(); now=-1;mmst(first,-1); re(i,1,m){int u=gint(),v=gint();addedge(u,v);degree[v]++;} ans=1; re(i,1,n)_degree[i]=degree[i]; degree[y]++; re(i,2,n)ans=ans*degree[i]%Mod; if(y==1){cout<<ans<<endl;return 0;} f[y]=ans; re(i,1,n)if(_degree[i]==0)Q.push(i); while(!Q.empty()) { int u=Q.front(),v;Q.pop(); for(i=first[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v) { (f[v]+=f[u])%=Mod; _degree[v]--; if(_degree[v]==0) { (f[v]*=power(degree[v],Mod-2))%Mod; Q.push(v); } } } ans-=f[x]; ans=(ans%Mod+Mod)%Mod; cout<<ans<<endl; return 0; }