BZOJ4307: Maishroom & Class

感觉有一点题面没有说得特别明确，就是一个人代替了其他人之后，另一个可以被他代替的人就不能让他来代替自己了。

每个人向自己可以代替的人连边，额外增加一个源点$r$向所有助教连边。第一问答案是$r$不能到达的点的个数。对于第二问，求出支配树，每个以$r$为父亲的点的子树中任选两个点都满足条件。

#include<cstdio>

struct edge{

	int v;

	edge*s;

};

template<int N,int M>

struct graph{

	edge*l,e[M],*h[N];

	graph():l(e){}

	void ins(int u,int v){

		*l={v,h[u]};

		h[u]=l++;

	}

};

const int N=5005;

const int M=25005;

graph<N,M>t1,t2;

graph<N,N>buc;

int n,f[N],par[N],semi[N],ver[N],dom[N],anc[N],lab[N];

void dfs(int u){

	semi[u]=++n;

	ver[n]=u;

	for(edge*i=t1.h[u];i;i=i->s)

		if(!semi[i->v]){

			par[i->v]=u;

			dfs(i->v);

		}

}

inline int eval(int u){

	if(anc[anc[u]]){

		eval(anc[u]);

		if(semi[lab[anc[u]]]<semi[lab[u]])

			lab[u]=lab[anc[u]];

		anc[u]=anc[anc[u]];

	}

	return lab[u];

}

void sol(int r){

	dfs(r);

	for(int i=1;i<=n;++i)

		lab[ver[i]]=ver[i];

	for(int i=n;i>=2;--i){

		int u=ver[i];

		for(edge*i=t2.h[u];i;i=i->s)

			if(semi[i->v]){

				int w=eval(i->v);

				if(semi[w]<semi[u])

					semi[u]=semi[w];

			}

		buc.ins(ver[semi[u]],u);

		anc[u]=par[u];

		for(edge*i=buc.h[par[u]];i;i=i->s){

			int w=eval(i->v);

			dom[i->v]=semi[w]<semi[i->v]?w:par[u];

		}

		buc.h[par[u]]=0;

	}

	for(int i=2;i<=n;++i){

		int u=ver[i];

		if(dom[u]!=ver[semi[u]])

			dom[u]=dom[dom[u]];

	}

}

void ins(int u,int v){

	t1.ins(u,v);

	t2.ins(v,u);

}

int main(){

	struct{

		operator int(){

			int x=0,c=getchar();

			while(c<48)

				c=getchar();

			while(c>47)

				x=x*10+c-48,c=getchar();

			return x;

		}

	}buf;

	int r=buf+1,l=buf;

	for(int u=1;u<=l;++u){

		int a=buf;

		while(a--)

			ins(buf,u);

	}

	for(int u=l+1;u<r;++u)

		ins(r,u);

	sol(r);

	int s=0;

	for(int i=n;i>=2;--i){

		int&a=f[ver[i]];

		int v=dom[ver[i]];

		f[v]+=++a;

		if(v==r)

			s+=a*(a-1)/2;

	}

	printf("%d %d\n",r-n,s);

}