「CTSC1999」家园 - 按时间拆点+动态加点最大流 | Bill Yang's Blog
0%

「CTSC1999」家园 - 按时间拆点+动态加点最大流

题目大意

    现有$n$个太空站处于地球与月球之间(编号$1\ldots n$),$m$艘公共交通太空船在其中来回穿梭,每个太空站$S_i$可容纳无限的人,每艘太空船$p_i$只可容纳$H_{p_i}$人。对于每一艘太空船$p_i$,将周期性地停靠一系列的太空站($S_{i_1},S_{i_2},\ldots,S_{i_r}$),如:($1,3,4$)表示停靠太空站$1\,3\,4\,1\,3\,4\,1\,3\,4\ldots。任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为$1$。人只能在太空船停靠太空站(或地球、月球)时上船或下船。初始时的人全在地球上,太空船全在初始站(太空船$p_i$处于$S_{i_1}$),目标是让所有的人尽快地全部转移到月球上。


题目分析

按照时间对每个星球拆点,枚举时间动态加边,动态求网络流,当剩余的运输人数$\le0$即可输出答案。


代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=5005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t);
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int n,m,k,map[25][25],Num[25],People[25];
#define All(cnt) (cnt)*(n+2)

int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
for(int i=1; i<=m; i++) {
People[i]=Get_Int();
Num[i]=Get_Int();
for(int j=1; j<=Num[i]; j++) {
map[i][j]=Get_Int();
if(map[i][j]==-1)map[i][j]=n+1;
}
}
for(int i=1; i<=80; i++) {
for(int j=0; j<=n+1; j++)dinic.AddEdge(All(i-1)+j,All(i)+j,INT_MAX/2); //停留
for(int j=1; j<=m; j++)dinic.AddEdge(All(i-1)+map[j][(i-1)%Num[j]+1],All(i)+map[j][i%Num[j]+1],People[j]); //运输
k-=dinic.maxflow(0,All(i)+n+1);
if(k<=0) {
printf("%d",i);
return 0;
}
}
puts("0");
return 0;
}
姥爷们赏瓶冰阔落吧~