POI 1999 洞穴探險 Speleology
本文正體字版由OpenCC轉換
這是一個網絡最大流問題。讀題發現有很明顯的模型,入口和出口的通道容量都是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<=N<=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