admin 管理员组

文章数量: 887021

家园

题目描述 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。

此题又是最大流模型，但是区别是这题的图是变化的。

以时间为序，对于每一个时刻，我们都得到一张图，然后我们对此使用dinic算法求最大流。

可以发现一个站可以有多个状态，我们以(i,j)表示i站在时刻j的状态，很显然(i,j-1)状态可以流向(i,j)状态，且容量为无穷大。

假设飞船k,j-1时刻到j时刻从s站到了t站，并且飞船的承载力为flow，则我们在途中应添加边(s,j-1)-->(t,j)，容量为flow。

所以对于时间每增加1，原图会增加n+2个点，也就是每个站会产生一个新状态，对于新图我们用dinic求最大流直到没有增广路，也就是从上一个时刻过渡到该时刻，又有多少人到达月球。

这里假定测试数据最大时间是小于等于100的，当时间超过100就认为无法全部到达月球。

#include<cstdio>
#include<iostream>
#include<cstring>
#define Maxn 3100
using namespace std;int flow[20],num[20],path[20][30];
const int inf=0x3f3f3f3f;
const int step=30;
struct line{int to,next,cap;
}p[Maxn*Maxn];
int head[Maxn];
int q[Maxn];
int d[Maxn];
int tot;
int src,t;
int n,m,k;
void addedge(int a,int b,int c){p[tot].to=b;p[tot].next=head[a];p[tot].cap=c;head[a]=tot++;
}
void insert(int a,int b,int c){addedge(a,b,c);addedge(b,a,0);
}
bool bfs(){memset(d,-1,sizeof d);int s=0,e=-1;q[++e]=src;d[src]=0;while(s<=e){int u=q[s++];for(int i=head[u];i!=-1;i=p[i].next){int v=p[i].to;if(d[v]==-1&&p[i].cap){d[v]=d[u]+1;q[++e]=v;}}}return d[t]!=-1;
}
int dfs(int u,int alpha){if(u==t) return alpha;int w,used=0;for(int i=head[u];i!=-1&&used<alpha;i=p[i].next){int v=p[i].to;if(p[i].cap&&d[v]==d[u]+1){w=dfs(v,min(alpha-used,p[i].cap));used+=w;p[i].cap-=w;p[i^1].cap+=w;}}if(!used) d[u]=-1;return used;
}
int dinic(int time){int ans=0;src=0,t=n+1+time*step;while(bfs())ans+=dfs(src,inf);return ans;
}
void add(int time){for(int i=0;i<n+2;i++)insert(i+(time-1)*step,i+time*step,inf);for(int i=0;i<m;i++)insert(path[i][(time-1)%num[i]]+(time-1)*step,path[i][time%num[i]]+time*step,flow[i]);
}
int main()
{int res;tot=0;memset(head,-1,sizeof head);cin>>n>>m>>k;for(int i=0;i<m;i++){cin>>flow[i]>>num[i];for(int j=0;j<num[i];j++){cin>>path[i][j];if(path[i][j]==-1)path[i][j]=n+1;}}for(res=1;res<=100;res++){add(res);k-=dinic(res);if(k<=0) break;}if(res<=100) cout<<res<<endl;else cout<<0<<endl;return 0;
}


本文标签： 家园

版权声明：本文标题：家园 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687782135h140765.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。