BZOJ1143:[CTSC2008]祭祀river(&&BZOJ2718) 二分图

思路:

首先是一个DAG.

然后,你要选出最多的点,使得任意两个点之间不能有到达关系.

考虑将拓扑图划分为若干条点不相交路径,那么所有的结束点之间都是不能到达的.

那么我们就要求出DAG的最小路径覆盖.

然而事实上由于是DAG,路径的点是可以相交的.于是我们通过拆点转化为一般的点不相交最小路径覆盖.

考虑给每一个点找一个入点,那么每出现一个匹配,路径的数目就会减少1.

于是利用总点数减去最大匹配即可.

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>

#define INF 0x3f3f3f3f

#define N 210
struct MaxflowSolver{
	static const int V=N<<1;
	static const int E=N*N<<1;
	int head[V],next[E],end[E],flow[E],ind;
	int d[V],gap[V],stk[V],top,cur[V];
	inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
	inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
	inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
	inline void bfs(int T){
		static int q[V];int fr=0,ta=0;
		memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
		while(fr^ta){
			int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
		}
	}
	inline int Maxflow(int S,int T,int cnt){
		int res=0,u=S,i,Min,ins;bfs(T),memcpy(cur,head,sizeof cur);
		while(d[S]<cnt){
			if(u==T){
				for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)Min=flow[stk[i]],ins=i;
				for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
				u=end[stk[top=ins]^1];
			}
			if(u!=T&&!gap[d[u]-1])break;
			bool find=0;
			for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
			if(find)cur[u]=stk[top++]=ins,u=end[ins];
			else{
				Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
				if(!--gap[d[u]])break;++gap[d[u]=Min+1];
				if(u!=S)u=end[stk[--top]^1];
			}
		}return res;
	}
}SteinsGate;

int head[N],next[N*N],end[N*N];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}

int seq[N],cnt;bool vis[N];
void dfs(int x){
	vis[x]=1,seq[++cnt]=x;
	for(int j=head[x];j;j=next[j])if(!vis[end[j]])dfs(end[j]);
}
int main(){
	int n,m;scanf("%d%d",&n,&m);register int i,j;
	int a,b;while(m--)scanf("%d%d",&a,&b),addedge(a,b);

	SteinsGate.reset();
	for(i=1;i<=n;++i){
		memset(vis,0,sizeof vis);
		cnt=0,dfs(i);
		for(j=1;j<=cnt;++j)if(seq[j]!=i)SteinsGate.make(i,n+seq[j],1);
	}

	int S=0,T=2*n+1;
	for(i=1;i<=n;++i)SteinsGate.make(0,i,1);
	for(i=1;i<=n;++i)SteinsGate.make(n+i,T,1);

	printf("%d",n-SteinsGate.Maxflow(S,T,2*n+2));

#ifndef ONLINE_JUDGE
	system("pause");
#endif
	return 0;
}