/****************************************\
* Author : ztx
* Title  : [POI1999] 洞穴探险
* ALG    : 网络流 最大流 ISAP算法
* CMT    :
题意: 给定有向无环图,起点为1,终点为n,问有多少人可以通过这个图
      要求在1处出发时每条边只可以走一个人,在n处聚集时,每条边只可以来一个人
分析: 所有连接 1 或 n 的边容量为 1 , 其它边容量为无穷 , 求最大流
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [POI1999] 洞穴探险
* ALG    : 网络流 最大流 ISAP算法
* CMT    :
题意: 给定有向无环图,起点为1,终点为n,问有多少人可以通过这个图
      要求在1处出发时每条边只可以走一个人,在n处聚集时,每条边只可以来一个人
分析: 所有连接 1 或 n 的边容量为 1 , 其它边容量为无穷 , 求最大流
* Time   :
\****************************************/

#include <cstdio>
#include <cstring>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define  maxn  210LL
#define  maxm  40010LL

struct FST { int to , next , flow ; } e[maxm<<1] ;
int star[maxn] , tote ;
inline void FST_init() { memset(star , 0 , sizeof star) ; tote = 1 ; }
inline void AddEdge(int u , int v , int cap) {
	e[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ;
	e[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}

#define  infi     0x3f3f3f3fLL
#define  min(x,y) ((x)<(y)?(x):(y))
int N , S , T ;
int h[maxn] , vh[maxn] ;

int dfs(int u , int flowu) {
int p , tmp = h[u]+1 , flow = 0 , flowv ;
	if (u == T) return flowu ;
	for (p = star[u] ; p ; p = e[p].next) {
		if (e[p].flow && (h[e[p].to]+1==h[u])) {
			flowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
			flow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
			if (flow==flowu || h[S]==N) return flow ;
		}
	}
	for (p = star[u] ; p ; p = e[p].next)
		if (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
	if (--vh[h[u]] == 0) h[S] = N ;
	else ++ vh[h[u]=tmp+1] ;
	return flow ;
}

int SAP() {
	int ret = 0 ;
	memset(vh , 0 , sizeof vh) ;
	memset(h , 0 , sizeof h) ;
	vh[S] = N ;
	while (h[S] < N) ret += dfs(S , infi) ;
	return ret ;
}

int n ;

int  i , u , v , m ;
inline void BuildGraph() {
	FST_init() ;
	read(m) ;
	for (i = 1 ; i <= m ; i ++ ) {
		read(v) ;
		AddEdge(1 , v , 1) ;
	}
	for (u = 2 ; u < n ; u ++ ) {
		read(m) ;
		for (i = 1 ; i <= m ; i ++ ) {
			read(v) ;
			if (v == n) AddEdge(u , v , 1) ;
			else AddEdge(u , v , infi) ;
		}
	}
	N = n , S = 1 , T = n ;
}

int main() {
	#define READ
	#ifdef  READ
		freopen("gro.in" ,"r",stdin ) ;
		freopen("gro.out","w",stdout) ;
	#endif
	read(n) ;
	BuildGraph() ;
	printf("%d\n", SAP() ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

• 相关文章
• 全局相关文章