星际转移问题
VanillaYuzume
·
·
题解
星际转移问题
题目:自己康
解法:(咱很菜 咱不知道怎么讲这一题)
根据题意 和样例数据 可以yy出下面这张图
每个点可能会存多次 而每条边也会根据时间变化发生改变
所以 我们以时间为基准 来进行分层
此时 问题就转变为 从0开始枚举时间 每次枚举时间后 添加一定量的边
使新图与旧图产生联系 当图中的最大流量比总人数大的时候 输出这时的时间
因为飞船会根据一定周期发生位置变化 所以我们可以通过 当前时间mod周期
当前时间 飞船所在的位置 和 飞船上一时间所在的位置
之后 我们把两个位置连在一起 其中 这条边的权值为飞船i的容量hp[i]
根据yy的图可以发现 以源点为0来计算
不同的点(出去源点和汇点)共有n+2个(n个太空站 地球 月球)
(下面n=n+2_(:зゝ∠)_)
**把每个空间站(包括地月)与它们在上一天的点连在一起**
```cpp
ae((day-1)*n+i,day*n+i,inf);
ae(day*n+i,(day-1)*n+i,0);
```
之后依次枚举每个飞船的情况 把飞船当前点与它们在上一天的点连在一起
(!注 每条边为飞船的容量
**代码酱 OVO↓**
```cpp
//CTSC1999 家园
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
#define N 500001
#define M 100
#define maxt 500
#define v to[i]
#define inf 0x7f7f7f7f
int n,m,k,s,t;
int sum,ans,day;//day:0->maxt
int dep[N],vis[N];
int ship[M][M],turn[M],hp[M];//船[i]在[j]时刻的位置 船i的循环周期 船i容量
int head[N],to[N],from[N],nex[N],w[N],ecnt;
void ae(int x,int y,int z){
from[ecnt]=x;
to[ecnt]=y;
w[ecnt]=z;
nex[ecnt]=head[x];
head[x]=ecnt++;
}
bool bfs(){
memset(dep,-1,sizeof(dep));
queue<int> q;
dep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=nex[i]){
if(dep[v]==-1 and w[i]>0){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t]!=-1;
}
int dfs(int u,int low){
if(u==t)
return low;
int ret=low;
for(int i=head[u];i!=-1;i=nex[i]){
if(dep[v]==dep[u]+1 and w[i]>0){
int flow=dfs(v,min(ret,w[i]));
if(flow>0){
w[i]-=flow;
w[i^1]+=flow;
}
ret-=flow;
if(!ret)
break;
}
}
return low-ret;
}
int dinic(){
int res=0;
while(bfs()){
res+=dfs(s,inf);
}
return res;
}
void init(){
int x;
scanf("%d%d%d",&n,&m,&k);
n+=2;//n=太空站数+2(地球+月球
for(int i=1;i<=m;i++){
scanf("%d%d",&hp[i],&turn[i]);
for(int j=1;j<=turn[i];j++){
scanf("%d",&ship[i][j]);
ship[i][j]+=2;//月球1 地球2 其他星球全+2
}
}
}
int main(){
init();
sum=0,day=0;
memset(head,-1,sizeof(head));
s=0,t=10000;//乱搞 把汇点设为一个很大的数
while(day<maxt){
ae(s,day*n+2,inf);//第day天的地球和源点连在一起
ae(day*n+2,s,0);
ae(day*n+1,t,inf);//第day天的月亮和汇点连在一起
ae(t,day*n+1,0);
if(day!=0){//如果不是第0天 即初状态
for(int i=1;i<=n;i++){//把同一星球前后两天连起来
ae((day-1)*n+i,day*n+i,inf);
ae(day*n+i,(day-1)*n+i,0);
}
for(int i=1;i<=m;i++){
//通过取余得到第day天 飞船i到循环的哪个地方
int x=ship[i][(day-1)%turn[i]+1];//上一个地方
int y=ship[i][day%turn[i]+1];//下一个地方
ae((day-1)*n+x,day*n+y,hp[i]);
ae(day*n+y,(day-1)*n+x,0);
}
}
sum+=dinic();
if(sum>=k)
break;
day++;
}
if(day==maxt){
printf("0\n");
return 0;
}
else{
printf("%d\n",day);
return 0;
}
return 0;
}
```