显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int SIZEm=20,SIZEN=1000,INF=0x7fffffff;
int load[SIZEm]={0};//即H,最大载客量
vector<int> table[SIZEm];//停靠表
int n,m,k;//太空站个数,太空船数量,人数
//地球是0,月球是1
class EDGE{
public:
int from,to,cap,flow;
};
vector<EDGE> edges;
int h[SIZEN]={0},e[SIZEN]={0};
vector<int> c[SIZEN];
queue<int> Q;//溢出点
int S=0,T=1;
int N;//当前图中的节点数,于是节点编号为0~N-1
void addedge(int from,int to,int cap){
if(from==to) return;
edges.push_back((EDGE){from,to,cap,0});
edges.push_back((EDGE){to,from,0,0});
int tot=edges.size()-2;
c[from].push_back(tot);
c[to].push_back(tot+1);
}
void push(int x,int k){//从x通过边k压
EDGE &now=edges[k];
if(now.flow>=now.cap) return;
int cf=min(e[x],now.cap-now.flow);
e[x]-=cf,e[now.to]+=cf,now.flow+=cf,edges[k^1].flow-=cf;
if(now.to!=S&&now.to!=T&&e[now.to]) Q.push(now.to);
}
void singlenode(int x){
int nowmin,u;
while(e[x]){
nowmin=INF;
for(int i=0;i<c[x].size();i++){
EDGE &now=edges[c[x][i]];
if(now.flow>=now.cap) continue;
u=now.to;
if(h[u]==h[x]-1){
push(x,c[x][i]);
if(!e[x]) return;
}
else nowmin=min(nowmin,h[u]);
}
h[x]=nowmin+1;
}
}
int maxflow(void){//对已经完备初始化的图进行网络流
for(int i=0;i<c[S].size();i++) push(S,c[S][i]);
while(!Q.empty()){
int x=Q.front();
Q.pop();
singlenode(x);
}
return e[T];
}
void makeday(int day){//新加上一天day,相应修改图,显然day>1,这里的day就是题中说的时刻
h[S]=N+n,e[S]=INF;//新加上了n个太空站节点
//其他的h和e均为现在的值,这个值开始的时候都是0
for(int i=1;i<=m;i++){
int u=table[i][day%table[i].size()];//这艘飞船第day天到了这一站
if(u>0) u+=N-1;
else if(u==-1) u=1;//u在图中应得的编号
int lt=table[i][(day-1)%table[i].size()];//这艘飞船第day-1天到了这一站
if(lt>0) lt+=(N-n-1);
else if(lt==-1) lt=1;//lt在图中的编号
addedge(lt,u,load[i]);//在这一天结束时,该航班从lt飞向了u
}
for(int i=1;i<=n;i++) addedge(N-1+i-n,N-1+i,INF);
N+=n;
}
void work(void){
N=n+2;//第0天的n+2个点
int ans;
for(ans=1;ans<=30;ans++){
makeday(ans);
if(maxflow()>=k){
printf("%d\n",ans);
return;
}
}
printf("0\n");
}
void read(void){
scanf("%d%d%d",&n,&m,&k);
int r,temp;
for(int i=1;i<=m;i++){
scanf("%d%d",&load[i],&r);
for(int j=1;j<=r;j++){
scanf("%d",&temp);
table[i].push_back(temp);
}
}
}
int main(){
freopen("home.in","r",stdin);
freopen("home.out","w",stdout);
read();
work();
return 0;
}
cstdio