竟然没有1A真羞耻...1分钟不到读完题,10分钟不到打完....MD没仔细看...WA了一遍,贱!

2929: [Poi1999]洞穴攀行

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 170 Solved: 85

[Submit][Status][Discuss]

Description

一队洞穴学者在Byte Mountain的Grate Cave里组织了一次训练。训练中，每一位洞穴学者要从最高的一个室到达最底下的一个室。他们只能向下走。一条路上每一个连续的室都要比它的前一个低。此外，每一个洞穴学者都要从最高的室出发，沿不同的路走到最低的室。问：可以有多少个人同时参加训练？

任务：

写一个程序：

l 读入对洞穴的描述。

l 计算可以同时参加训练的人数。

l 将结果输出。

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

HINT

Source

直接连边,套上模版A!

哦对…开头和结尾容量为1….

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int read()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

#define maxn 210

#define inf 0x7fffffff

struct data{int to,next,cap;}edge[2*maxn*maxn];

int n;int m;

int head[maxn*maxn*2],cnt=1;

int cur[maxn*maxn*2];

int S,T;

void add(int u,int v,int w)

{

    cnt++;

    edge[cnt].next=head[u]; head[u]=cnt;

    edge[cnt].to=v; edge[cnt].cap=w;

}

void insert(int u,int v,int w)

{

    add(u,v,w);add(v,u,0);

}

int q[10000],h,t,dis[10000];

bool bfs()

{

    memset(dis,-1,sizeof(dis));

    q[1]=S; dis[S]=1;

    h=0;t=1;

    while (h<t)

        {

            int j=q[++h],i=head[j];

            while (i)

                {

                    if (edge[i].cap>0 && dis[edge[i].to]<0)

                        {

                            dis[edge[i].to]=dis[j]+1;

                            q[++t]=edge[i].to;

                        }

                    i=edge[i].next;

                }

        }

   return dis[T]>0;

}

int dfs(int loc,int low)

{

    if(loc==T) return low;

    int flow,cost=0;

    for(int i=cur[loc];i;i=edge[i].next)

        if(dis[edge[i].to]==dis[loc]+1)

            {

                flow=dfs(edge[i].to,min(low-cost,edge[i].cap));

                edge[i].cap-=flow;edge[i^1].cap+=flow;

                if(edge[i].cap) cur[loc]=i;

                cost+=flow; if(cost==low) return low;

            }

    if(!cost) dis[loc]=-1;

    return cost;

}

int dinic()

{

    double ans=0;

    while (bfs())

        {

           for (int i=S; i<=T; i++) cur[i]=head[i];

           ans+=dfs(S,inf);

        }

    return ans;

}

int main()

{

    n=read();

    for (int i=1; i<=n-1; i++)

        {

            m=read();

            for (int j=1; j<=m; j++)

                {

                    int v=read();

                    if (i==1 || v==n) insert(i,v,1);

                                 else insert(i,v,inf);

                }

        }

    S=1;T=n;

    int ans=dinic();

    printf("%d\n",ans);

    return 0;

}