「CODEVS1034」家园
题目描述 Description
由于人类对自然的疯狂破坏，人们意识到在大约2300年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。
现有n个太空站处于地球与月球之间（编号1..n），m艘公共交通太空船在其中来回穿梭，每个太空站Si可容纳无限的人，每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi，将周期性地停靠一系列的太空站（Si1,Si2…Sir），如：（1，3，4）表示停靠太空站1 3 4 1 3 4 1 3 4 …。 任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站（或地球、月球）时上船或下船。初始时的人全在地球上，太空船全在初始站（太空船pi处于Si1），目标是让所有的人尽快地全部转移到月球上。
输入描述 Input Description
文件第一行为三个正整数 n（太空站个数）、 m（太空船个数）、 k（需要运送的地球上的人的个数），其中 1<=m<=13, 1<=n<=20, 1<=k<=50。
接下来的n行给出了太空船的信息，第i+1行说明太空船pi，此行第一个数表示pi可容纳的人数Hpi，第二个数表示pi停靠一个周期的太空站个数r，1<=r<=n+2, 随后r个数便是停靠的太空站的编号(Si1,Si2,…,Sir), 地球用0表示，月球用-1表示。0时刻时，所有太空船都在初始站，随后开始运行，在时刻1，2，3…等正点时刻各艘太空船停靠相应的太空站，即人只有在0,1,2…等正点时刻才能上下太空船。
输出描述 Output Description
文件只有一个数，若问题有解，输出完成全部人员安全转移的时刻，否则输出0。
样例输入 Sample Input
2 2 1
1 3 0 1 2
1 3 1 2 –1
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
1<=m<=13, 1<=n<=20, 1<=k<=50。
题解
拆点
每次时间 T++，
｛
然后每个节点（空间站，地球，月球）增加一个分点。
对于每次的T 由 第i个节点的T号分点 向第 i个节点的（T+1）号分点连一条容量无限的边 再由 第j艘飞船T时刻所在空间站的T号分点 向 第j飞船T+1时刻所在空间站的T+1号分点 连一条容量为h[j]的边
跑一遍dinic
如果 k小于等于0 输出此刻的T
如果T大于100（数据比较弱，做下来运完的都在100以内） 输出0
｝
差不多这样。。
注意样例的 -1的负号有问题
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #define inf 0x7fffffff using namespace std; int n,m,k,T,cnt=1; int a[25][25],s[25],H[25]; int q[4001],h[4001],head[4001]; struct data{int to,next,v;}e[50001]; void ins(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} void add() { for(int i=0;i<=n+1;i++) insert(i+(T-1)*22,i+T*22,inf); for(int i=1;i<=m;i++) { int u=(T-1)*22+a[i][(T-1)%s[i]+1]; int v=T*22+a[i][T%s[i]+1]; insert(u,v,H[i]); } } bool bfs() { int t=0,w=1,i,now; memset(h,-1,sizeof(h)); h[0]=q[0]=0; while(t<w) { now=q[t];t++; i=head[now]; while(i) { if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;} i=e[i].next; } } if(h[1+n+T*22]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==1+n+T*22)return f; int i=head[x]; int w,used=0; while(i) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w; e[i^1].v+=w; used+=w; if(used==f)return f; } i=e[i].next; } if(!used)h[x]=-1; return used; } void dinic(){while(bfs())k-=dfs(0,inf);} int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { scanf("%d%d",&H[i],&s[i]); for(int j=1;j<=s[i];j++) { scanf("%d",&a[i][j]); if(a[i][j]==-1)a[i][j]=n+1; } } for(T=1;T<=100;T++) { add(); dinic(); if(k<=0){printf("%d",T);return 0;} } printf("0"); return 0; } |
OI 课件=>
