2929: [Poi1999]洞穴攀行
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 388 Solved: 215
Description
洞穴学者在Byte Mountain的Grate Cave里组织了一次训练。训练中，每一位洞穴学者要从最高的一个室到达最底下的一个室。他们只能向下走。一条路上每一个连续的室都要比它的前一个低。此外，每一个洞穴学者都要从最高的室出发，沿不同的路走到最低的室。
限制：
1.起点连接的通道同一时间只能容纳一个人通过
2.终点连接的通道同一时间只能容纳一个人通过
3.其他边都很宽敞，同一时间可以容纳无限多的人
问：可以有多少个人同时参加训练？
Input
第一行有一个整数n(2<=n<=200)，等于洞穴中室的个数。用1~n给室标号，号码越大就在越下面。最高的室记为1，最低的室记为n。以下的n-1行是对通道的描述。第I+1行包含了与第I个室有通道的室（只有比标号比I大的室）。这一行中的第一个数是m,0<=m<=(n-i+1)，表示被描述的通道的个数。接着的m个数字是与第I个室有通道的室的编号。
Output
输出一个整数。它等于可以同时参加训练的洞穴学者的最大人数。
Sample Input
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
Sample Output
3
赤果果的最大流裸题
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f*x;
}
const int N=210;const int inf=0X7f7f7f7f;
int n,ecnt=1,last[N],cur[N],q[N],d[N],S=1,T,ans;
struct EDGE{int to,nt,val;}e[N*N];
inline void readd(int u,int v,int val)
{e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;}
inline void add(int u,int v,int val)
{readd(u,v,val);readd(v,u,0);}
bool bfs()
{
memset(d,0,sizeof(d));
int head=0,tail=1;q[head]=S;d[S]=1;
while(head<tail)
{
int u=q[head++];//cout<<u<<endl;
for(int i=last[u];i;i=e[i].nt)
if(e[i].val&&!d[e[i].to])
{
d[e[i].to]=d[u]+1;
q[tail++]=e[i].to;
}
}
return d[T];
}
int dfs(int u,int lim)
{
if(u==T||!lim)return lim;
int flow=0;
for(int i=cur[u];i;i=e[i].nt)
if(d[u]+1==d[e[i].to])
{
int tmp=dfs(e[i].to,min(e[i].val,lim));
e[i].val-=tmp;e[i^1].val+=tmp;flow+=tmp;lim-=tmp;
if(e[i].val)cur[e[i].to]=i;if(!lim)break;
}
if(!flow)d[u]=-1;
return flow;
}
void dinic()
{while(bfs()){for(int i=1;i<=n;i++)cur[i]=last[i];ans+=dfs(S,inf);}}
int main()
{
n=read();int num=read(),v;T=n;
while(num--)v=read(),add(S,v,1);
for(int i=2;i<n;i++)
{num=read();while(num--){v=read();if(v!=T)add(i,v,inf);else add(i,T,1);}}
dinic();
printf("%d\n",ans);return 0;
}