「BZOJ2929」[POI1999] 洞穴攀行
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
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
题解
题解。。
裸网络流
话说好像可以用匈牙利
顺便说下题意，1出发以及到达n的边只能走一次，其余随意
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,cnt=1,ans; int h[205],q[205],last[205],cur[205]; struct edge{ int to,next,v; }e[40005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0; } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); h[1]=0;q[0]=1; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[n]!=-1; } int dfs(int x,int f) { if(x==n)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) if(h[x]+1==h[e[i].to]) { w=f-used; w=dfs(e[i].to,min(e[i].v,w)); e[i].v-=w;e[i^1].v+=w; if(e[i].v)cur[x]=i; used+=w; if(used==f)return f; } if(!used)h[x]=-1; return used; } void dinic() { while(bfs()) { for(int i=1;i<=n;i++) cur[i]=last[i]; ans+=dfs(1,inf); } } int main() { n=read(); int x; for(int i=1;i<n;i++) { x=read(); while(x--) { int v=read(); if(i==1||v==n)insert(i,v,1); else insert(i,v,inf); } } dinic(); printf("%d",ans); return 0; } |
计数器 9874358
OI 课件=>
OI 课件=>
感觉这个题目有点奇怪。走不同的路具体指什么？
可以无视中文翻译
这题的翻译职业报复社会几十年
if(e
.v)cur 
=i; 这一句是什么意思?起什么作用?cur 
是否是当前节点x的邻居节点?
噢这是当前弧优化
您能具体解释一下吗?
就是每个点从还没有流满的边开始访问，无视满流的出边
诶我发现我优化似乎写错位置了233
是否就是当下一次递归到x节点时,就不在从x节点的1号邻居节点开始枚举了(因为之前已经枚举了)而是从cur
号邻居节点开始?
恩。。。所以这个应该写在dfs前面。。我之前位置放错了
能麻烦你把修改后的代码和测试数据发我一份吗?1063027816@qq.com,你的代码很值的我学习
代码在这了。。。数据没有
多谢你的帮助!