记录编号 |
430582 |
评测结果 |
AAAAAAAAAAA |
题目名称 |
[POI 1999] 洞穴探险 |
最终得分 |
100 |
用户昵称 |
Hzoi_Mafia |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.000 s |
提交时间 |
2017-07-30 06:47:17 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
int sum(0);
char ch(getchar());
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
return sum;
}
struct edge{
int e,flow,n;
}a[40001];
int pre[201],tot;
inline void insert(int s,int e,int flow){
a[tot].e=e;
a[tot].flow=flow;
a[tot].n=pre[s];
pre[s]=tot++;
}
int n;
int ans(0),inf(0xfffffff);
int dis[201];
inline bool bfs(int s,int t){
memset(dis,0,sizeof(dis));
dis[s]=1;
queue<int>q;
q.push(s);
while(!q.empty()){
int k(q.front());
q.pop();
for(int i=pre[k];i!=-1;i=a[i].n){
int e(a[i].e);
if(!dis[e]&&a[i].flow){
dis[e]=dis[k]+1;
q.push(e);
if(e==t)
return true;
}
}
}
return false;
}
inline int my_min(int a,int b){
return a<b?a:b;
}
inline int dfs(int now,int flow){
if(now==n)
return flow;
int tmp(flow),f;
for(int i=pre[now];i!=-1;i=a[i].n){
int e(a[i].e);
if(dis[e]==dis[now]+1&&tmp&&a[i].flow){
f=dfs(e,my_min(tmp,a[i].flow));
if(!f){
dis[e]=0;
continue;
}
a[i].flow-=f;
a[i^1].flow+=f;
tmp-=f;
}
}
return flow-tmp;
}
inline int gg(){
freopen("gro.in","r",stdin);
freopen("gro.out","w",stdout);
memset(pre,-1,sizeof(pre));
n=read();
for(int i=1;i<n;i++){
int x(read());
for(int j=1;j<=x;j++){
int y(read());
if(y<=i)
continue;
insert(y,i,0);
if(y==n||i==1)
insert(i,y,1);
else
insert(i,y,inf);
}
}
while(bfs(1,n))
ans+=dfs(1,inf);
printf("%d",ans);
}
int K(gg());
int main(){;}