Beyond the Void
BYVoid
POI 1999 洞穴探险 Speleology

这是一个网络最大流问题。读题发现有很明显的模型,入口和出口的通道容量都是1,内部通道没有容量限制,求从1到N最多通过的人数。

源为1,汇为N,把连接源和汇的通道建立为容量为1的边,其余的边容量为无限,求从源到汇的网络最大流就是结果。

题中所给N<=200,可以用一般的最大流算法解决。我的程序是Dinic。

/* 
 * Problem: POI1999 gro
 * Author: Guo Jiabao
 * Time: 2008.12.14 10:00:32
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=201;
const int INF=0x7FFFFFFF;

struct edge
{
	int c,t;
	edge *next,*op;
};

struct adjl
{
	edge *f,*l;
};

edge E[MAX*MAX];
adjl A[MAX];
edge *P[MAX],*Stae[MAX];
int N,S,T,Ec,Maxflow;
int Lv[MAX],Que[MAX],Stap[MAX];

edge* adjl_ins(adjl &L,int t,int c)
{
	if (!L.f)
		L.f=L.l=&E[Ec];
	else
		L.l=L.l->next=&E[Ec];
	E[Ec].c=c;
	E[Ec].t=t;
	E[Ec].next=0;
	return &E[Ec++];
}

void addedge(int a,int b,int v)
{
	edge *pa,*pb;
	pa=adjl_ins(A[a],b,v);
	pb=adjl_ins(A[b],a,0);
	pa->op=pb;
	pb->op=pa;
}

void init()
{
	int i,j,p,t,v;
	freopen("gro.in","r",stdin);
	freopen("gro.out","w",stdout);
	scanf("%d",&N);
	S=1;T=N;
	for (i=1;i<=N;i++)
	{
		A[i].f=0;
	}
	for (i=1;i<=N;i++)
	{
		scanf("%d",&p);
		for (j=1;j<=p;j++)
		{
			scanf("%d",&t);
			v=1;
			if (i!=S && i!=T && t!=S && t!=T)
				v=INF;
			addedge(i,t,v);
		}
	}
	
}

bool Dinic_Level()
{
	int Head,Tail,i,j,c;
	edge *k;
	memset(Lv,0,sizeof(Lv));
	Lv[S]=1;
	Que[Head=0,Tail=0]=S;
	while (Head<=Tail)
	{
		i=Que[Head++];
		for (k=A[i].f;k;k=k->next)
		{
			j=k->t; c=k->c;
			if (Lv[j]==0 && c>0)
			{
				Lv[j]=Lv[i]+1;
				Que[++Tail]=j;
			}
		}
	}
	return Lv[T]!=0;
}

int Dinic_Flow()
{
	int i,u,v,top=0,flow=0,delta,rtn;
	for (i=S;i<=T;i++)
		P[i]=A[i].f;
	Stap[++top]=S;
	while (top)
	{
		u=Stap[top];
		if (u!=T)
		{
			while (P[u] && (P[u]->c<=0 || Lv[u]+1!=Lv[ v=P[u]->t ]) )
				P[u]=P[u]->next;
			if (P[u])
			{
				v=P[u]->t;
				Stap[++top]=v;
				Stae[top]=P[u];
				P[u]=P[u]->next;
			}
			else
				top--;
		}
		else
		{
			delta=INF;
			for (i=top;i>=2;i--)
				if (Stae[i]->c < delta)
					delta=Stae[i]->c;
			flow+=delta;
			for (i=top;i>=2;i--)
			{
				Stae[i]->c-=delta;
				Stae[i]->op->c+=delta;
				if (Stae[i]->c==0)
					rtn=i-1;
			}
			top=rtn;
		}
	}
	return flow;
}

void Dinic()
{
	while (Dinic_Level())
		Maxflow+=Dinic_Flow();
}

int main()
{
	init();
	Dinic();
	printf("%d",Maxflow);
	return 0;
}
<h2><span class="mw-headline">洞穴探险</span></h2>

问题描述

古老的Byte山上有一处神秘的连环洞穴。考古学家们为了对这个洞穴进行研究,组织了一次探险活动。他们花了几天的时间仔细地翻阅了前人留下的资料,对该连环洞穴有了大致的了解。

这是一个有许多不同的小溶洞组成的连环洞穴,每个小溶洞都分布在不同的地层中,并且可能通过洞穴隧道与其他小溶洞相通。

考古学家们已经发现了作为连环洞穴的入口的一个小溶洞,并且根据前人的资料,绘制出了洞穴的地图,标明了哪些小溶洞之间是有洞穴隧道相连的。

富有冒险和激情的考古学家们都期望自己能够独自进行探险活动。于是,他们又提出了这样的要求:从入口的溶洞出发时,每个人都选择一条不同的 洞穴隧道前进;探险结束时,每个人都是通过不同的洞穴隧道抵达最底层的小溶洞。当然了,这些考古学家也达成了妥协:在探险的过程中,可以有不止一名的考古 学家通过同一条洞穴隧道。 为了体现这次探险活动的一往直前的精神,考古学家们还决定,要从小溶洞入口进入,一直抵达最底层的溶洞!每个考古学家探险路线上通过的小溶洞所在的地层必 须比该路线上前一个溶洞的地层低。

考古学家提出来如此多的要求使得本次探险活动的组织者犯了愁,他究竟最多能邀请多少位考古学家来参加这项活动呢?

输入文件

第一行是一个数N(2&lt;=N&lt;=200),表示小溶洞的总数。每个小溶洞用一个数字标号,标号越大,该小溶洞的所在地层越低。入口的小溶洞标号为1,最底层的小溶洞标号为N。

以下共有N-1行,第i+1行表示的是标号为i个溶洞与哪些溶洞相连。每行第一个数字是Mi,表示共与Mi个溶洞相连,随后是Mi个数字,为这些溶洞的标号。

输出文件

输出文件只有一行,为一个整数,表示的是最多能有多少位考古学家参加这次活动。

样例输入
<pre>12
4 3 4 2 5
1 8
2 9 7
2 6 11
1 8
2 9 10
2 10 11
1 12
2 10 12
1 12
1 12</pre>
该数据描述的是下面这样一个连环洞穴:

<a class="image" title="Image:Gro.png" href="http://www.ruvtex.cn/wiki/Image:Gro.png"><img src="http://www.ruvtex.cn/mw/images/b/be/Gro.png" alt="Image:Gro.png" width="249" height="426" /></a>

样例输出
<pre>3</pre>

上次修改时间 2017-05-22

相关日志