poj 1698

98 阅读 0 评论 65 点赞

我是靠谱客的博主专注航空，这篇文章主要介绍poj 1698，现在分享给大家，希望可以做个参考。

题意:爱丽丝喜欢拍电影,现在正好有N个公司找她拍电影,每部电影都指定在每周的星期几拍,要用D天拍完电影,最迟M个星期要拍完.问爱丽丝能不能拍完所有电影.

分析:350天各为一个顶点,每个顶点都有且只有一条边指向汇点t,容量为1,源点为爱丽丝,指向每部电影,权值为该部电影拍完的天数D,每部电影都向能拍这部电影的那一天的顶点建一条权值为1的边.如果计算出来的最大流为所有电影要拍的天数的总和则能够拍完所有电影,否则不能.

复制代码

1 #include <cstdio>

2 #include <cstring>

3 const int MAXN=375;//点数的最大值

4 const int MAXM=14740;//边数的最大值

5 const int INF=0x3fffffff;

7 struct Node

8 {

9
int from,to,next;
 10
int cap;
 11 }edge[MAXM];
 12
 13 int tol;
 14 int head[MAXN];
 15 int dep[MAXN];
 16 int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y
 17
 18 int n;//n是总的点的个数，包括源点和汇点
 19
 20 void init()
 21 {
 22
tol=0;
 23
memset(head,-1,sizeof(head));
 24 }
 25
 26 void addedge(int u,int v,int w)
 27 {
 28
edge[tol].from=u;
 29
edge[tol].to=v;
 30
edge[tol].cap=w;
 31
edge[tol].next=head[u];
 32
head[u]=tol++;
 33
edge[tol].from=v;
 34
edge[tol].to=u;
 35
edge[tol].cap=0;
 36
edge[tol].next=head[v];
 37
head[v]=tol++;
 38 }
 39 void BFS(int start,int end)
 40 {
 41
memset(dep,-1,sizeof(dep));
 42
memset(gap,0,sizeof(gap));
 43
gap[0]=1;
 44
int que[MAXN];
 45
int front,rear;
 46
front=rear=0;
 47
dep[end]=0;
 48
que[rear++]=end;
 49
while(front!=rear)
 50 
{
 51
int u=que[front++];
 52
if(front==MAXN)front=0;
 53
for(int i=head[u];i!=-1;i=edge[i].next)
 54 
{
 55
int v=edge[i].to;
 56
if(dep[v]!=-1)continue;
 57
que[rear++]=v;
 58
if(rear==MAXN)rear=0;
 59
dep[v]=dep[u]+1;
 60
++gap[dep[v]];
 61 
}
 62 
}
 63 }
 64 int SAP(int start,int end)
 65 {
 66
int res=0;
 67 
BFS(start,end);
 68
int cur[MAXN];
 69
int S[MAXN];
 70
int top=0;
 71
memcpy(cur,head,sizeof(head));
 72
int u=start;
 73
int i;
 74
while(dep[start]<n)
 75 
{
 76
if(u==end)
 77 
{
 78
int temp=INF;
 79
int inser;
 80
for(i=0;i<top;i++)
 81
if(temp>edge[S[i]].cap)
 82 
{
 83
temp=edge[S[i]].cap;
 84
inser=i;
 85 
}
 86
for(i=0;i<top;i++)
 87 
{
 88
edge[S[i]].cap-=temp;
 89
edge[S[i]^1].cap+=temp;
 90 
}
 91
res+=temp;
 92
top=inser;
 93
u=edge[S[top]].from;
 94 
}
 95
if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路
 96
break;
 97
for(i=cur[u];i!=-1;i=edge[i].next)
 98
if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)
 99
break;
100
if(i!=-1)
101 
{
102
cur[u]=i;
103
S[top++]=i;
104
u=edge[i].to;
105 
}
106
else
107 
{
108
int min=n;
109
for(i=head[u];i!=-1;i=edge[i].next)
110 
{
111
if(edge[i].cap==0)continue;
112
if(min>dep[edge[i].to])
113 
{
114
min=dep[edge[i].to];
115
cur[u]=i;
116 
}
117 
}
118
--gap[dep[u]];
119
dep[u]=min+1;
120
++gap[dep[u]];
121
if(u!=start)u=edge[S[--top]].from;
122 
}
123 
}
124
return res;
125 }
126 int main()
127 {
128
int T,N,f[7],D,W;
129
scanf("%d",&T);
130
n = 372;
131
int s = 370,t = 371;
132
while(T--)
133 
{
134
scanf("%d",&N);
135 
init();
136
int sum = 0;
137
for(int i = 0;i < N;i++)
138 
{
139
for(int j = 0;j < 7;j++)
140 
{
141
scanf("%d",&f[j]);
142 
}
143
scanf("%d%d",&D,&W);
144
sum += D;
145
for(int j = 0;j < 7;j++)
146 
{
147
if(f[j])
148 
{
149
for(int k = 0;k < W;k++)
150 
{
151
addedge(350 + i,k * 7 + j,1);
152 
}
153 
}
154 
}
155
addedge(s,350 + i,D);
156 
}
157
for(int j = 0;j < 350;j++)
158 
{
159
addedge(j,t,1);
160 
}
161
if(SAP(s,t) == sum)
162
printf("Yesn");
163
else
164
printf("Non");
165 
}
166 }

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308

1 #include <cstdio>

2 #include <cstring>

3 const int MAXN=375;//点数的最大值

4 const int MAXM=14740;//边数的最大值

5 const int INF=0x3fffffff;

6

7 struct Node

8 {

9
int from,to,next;
 10
int cap;
 11 }edge[MAXM];
 12
 13 int tol;
 14 int head[MAXN];
 15 int dep[MAXN];
 16 int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y
 17
 18 int n;//n是总的点的个数，包括源点和汇点
 19
 20 void init()
 21 {
 22
tol=0;
 23
memset(head,-1,sizeof(head));
 24 }
 25
 26 void addedge(int u,int v,int w)
 27 {
 28
edge[tol].from=u;
 29
edge[tol].to=v;
 30
edge[tol].cap=w;
 31
edge[tol].next=head[u];
 32
head[u]=tol++;
 33
edge[tol].from=v;
 34
edge[tol].to=u;
 35
edge[tol].cap=0;
 36
edge[tol].next=head[v];
 37
head[v]=tol++;
 38 }
 39 void BFS(int start,int end)
 40 {
 41
memset(dep,-1,sizeof(dep));
 42
memset(gap,0,sizeof(gap));
 43
gap[0]=1;
 44
int que[MAXN];
 45
int front,rear;
 46
front=rear=0;
 47
dep[end]=0;
 48
que[rear++]=end;
 49
while(front!=rear)
 50 
{
 51
int u=que[front++];
 52
if(front==MAXN)front=0;
 53
for(int i=head[u];i!=-1;i=edge[i].next)
 54 
{
 55
int v=edge[i].to;
 56
if(dep[v]!=-1)continue;
 57
que[rear++]=v;
 58
if(rear==MAXN)rear=0;
 59
dep[v]=dep[u]+1;
 60
++gap[dep[v]];
 61 
}
 62 
}
 63 }
 64 int SAP(int start,int end)
 65 {
 66
int res=0;
 67 
BFS(start,end);
 68
int cur[MAXN];
 69
int S[MAXN];
 70
int top=0;
 71
memcpy(cur,head,sizeof(head));
 72
int u=start;
 73
int i;
 74
while(dep[start]<n)
 75 
{
 76
if(u==end)
 77 
{
 78
int temp=INF;
 79
int inser;
 80
for(i=0;i<top;i++)
 81
if(temp>edge[S[i]].cap)
 82 
{
 83
temp=edge[S[i]].cap;
 84
inser=i;
 85 
}
 86
for(i=0;i<top;i++)
 87 
{
 88
edge[S[i]].cap-=temp;
 89
edge[S[i]^1].cap+=temp;
 90 
}
 91
res+=temp;
 92
top=inser;
 93
u=edge[S[top]].from;
 94 
}
 95
if(u!=end&&gap[dep[u]-1]==0)//出现断层，无增广路
 96
break;
 97
for(i=cur[u];i!=-1;i=edge[i].next)
 98
if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1)
 99
break;
100
if(i!=-1)
101 
{
102
cur[u]=i;
103
S[top++]=i;
104
u=edge[i].to;
105 
}
106
else
107 
{
108
int min=n;
109
for(i=head[u];i!=-1;i=edge[i].next)
110 
{
111
if(edge[i].cap==0)continue;
112
if(min>dep[edge[i].to])
113 
{
114
min=dep[edge[i].to];
115
cur[u]=i;
116 
}
117 
}
118
--gap[dep[u]];
119
dep[u]=min+1;
120
++gap[dep[u]];
121
if(u!=start)u=edge[S[--top]].from;
122 
}
123 
}
124
return res;
125 }
126 int main()
127 {
128
int T,N,f[7],D,W;
129
scanf("%d",&T);
130
n = 372;
131
int s = 370,t = 371;
132
while(T--)
133 
{
134
scanf("%d",&N);
135 
init();
136
int sum = 0;
137
for(int i = 0;i < N;i++)
138 
{
139
for(int j = 0;j < 7;j++)
140 
{
141
scanf("%d",&f[j]);
142 
}
143
scanf("%d%d",&D,&W);
144
sum += D;
145
for(int j = 0;j < 7;j++)
146 
{
147
if(f[j])
148 
{
149
for(int k = 0;k < W;k++)
150 
{
151
addedge(350 + i,k * 7 + j,1);
152 
}
153 
}
154 
}
155
addedge(s,350 + i,D);
156 
}
157
for(int j = 0;j < 350;j++)
158 
{
159
addedge(j,t,1);
160 
}
161
if(SAP(s,t) == sum)
162
printf("Yesn");
163
else
164
printf("Non");
165 
}
166 }