做题的时候看到了这个算法，决定学习一下。

一个有向图，给定一个点，求以该点为根的最小生成树。

具体做法是这样的：先找到每个点最小的入边，如果没有环，那么这就是最小生成树。

不然就要在环中删边，并把这些环连起来。

例如点1,2形成了环，如果点3连向点，那么肯定也只能删的是（2,1）这条边。

所以可以缩点，然后缩点后的边就是原来的权值减去入点的最小入边。

递归即可。复杂度O（VE）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 2000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 110
#define M 10100
struct poi
{
	double x,y;
}p[N];
struct xfy
{
	int x,y;double w;
	xfy(){}
	xfy(int _x,int _y,double _w):x(_x),y(_y),w(_w){}
}eg[M];

int n,m,V,x,y;
double sqr(double x)
{
	return x*x;
}

double dis(int x,int y)
{
	return sqrt(sqr(p[x].x-p[y].x)+sqr(p[x].y-p[y].y));
}
double in[N];
int pre[N],id[N],vis[N];
double mst(int rt,int n,int m)
{
	double ret = 0;
	for (;;)
	{
		rep(i,1,n) in[i] = inf;
		rep(i,1,m)
		{
			int x = eg[i].x,y = eg[i].y;
			if (eg[i].w < in[y]) in[y] = eg[i].w,pre[y] = x;
		}
		rep(i,1,n)
		{
			if (i == rt) continue;
			if (in[i] == inf) return -1;
		}
		int cnt = 0,len = 0; in[rt] = 0;
		clr(id,0); clr(vis,0);
		rep(i,1,n)
		{
			ret += in[i];
			int x = i;
			for (;vis[x] != i && !id[x] && x != rt;x = pre[x]) vis[x] = i;
			if (x != rt && !id[x])
			{
				id[x] = ++cnt;
				for (int u = pre[x];u != x;u = pre[u]) id[u] = cnt;
			}
		}
		if (cnt == 0) return ret;
		rep(i,1,n) if (!id[i]) id[i] = ++cnt;
		rep(i,1,m)
		{
			int x = eg[i].x,y = eg[i].y;
			if (id[x] == id[y]) continue;
			eg[++len] = xfy(id[x],id[y],eg[i].w-in[y]);
		}
		rt = id[rt];
		n = cnt;
		m = len;
	}
	return ret;
}

			
int main()
{
	for (;scanf("%d%d",&n,&m)!=EOF;V = 0)
	{
		rep(i,1,n) scanf("%lf%lf",&p[i].x,&p[i].y);
		rep(i,1,m)
		{
			scanf("%d%d",&x,&y);
			if (x == y) continue;
			eg[++V] = xfy(x,y,dis(x,y));
		}
		double ans = mst(1,n,V);
		if (ans < 0) puts("poor snoopy");
		else printf("%.2lf\n",ans);
	}
	return 0;
}

[bzoj4011]一个DAG+1条s->t的边，求以1为根的生成树数量。

朱刘算法推论:DAG上的生成树数量=deg[2]*……deg[n](1为根时）

加一条边，考虑容斥即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
#define M 200010

int n,m,s,t,rd[N],deg[N],x,y;
ll inv[M],f[N],ans=1;
int h[M],last[M],head[N],l;
queue<int> q;
void add(int x,int y)
{
	h[++l] = y;
	last[l] = head[x];
	head[x] = l;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	rep(i,1,m)
	{
		scanf("%d%d",&x,&y);
		rd[y]++; deg[y]++;
		add(x,y);
	}
	inv[1] = 1;
	rep(i,2,m+1) inv[i] = (zhl-zhl/i)*inv[zhl%i]%zhl;
	deg[t]++;
	rep(i,2,n) ans = ans*deg[i]%zhl;
	if (t == 1) return printf("%lld",ans),0;
	rep(i,1,n) if (!rd[i]) q.push(i);
	f[t] = ans;
	for (;!q.empty();q.pop())
	{
		x = q.front();
		f[x] = f[x]*inv[deg[x]]%zhl;
		for (int i = head[x],y;i;i = last[i])
		{
			y = h[i]; f[y] = (f[y]+f[x])%zhl;
			if (!--rd[y]) q.push(y);
		}
	}
	printf("%lld\n",(ans-f[s]+zhl)%zhl);
	return 0;
}