# [POJ 1698] Alice's Chance【网络流(EK/Dinic/ISAP)】

• 2018-01-14
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 10000K

Description

Alice, a charming girl, have been dreaming of being a movie star for long. Her chances will come now, for several filmmaking companies invite her to play the chief role in their new films. Unfortunately, all these companies will start making the films at the same time, and the greedy Alice doesn't want to miss any of them!! You are asked to tell her whether she can act in all the films.

As for a film,

1. it will be made ONLY on some fixed days in a week, i.e., Alice can only work for the film on these days;
2. Alice should work for it at least for specified number of days;
3. the film MUST be finished before a prearranged deadline.

For example, assuming a film can be made only on Monday, Wednesday and Saturday; Alice should work for the film at least for 4 days; and it must be finished within 3 weeks. In this case she can work for the film on Monday of the first week, on Monday and Saturday of the second week, and on Monday of the third week.

Notice that on a single day Alice can work on at most ONE film.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a single line containing an integer N (1 <= N <= 20), the number of films. Each of the following n lines is in the form of "F1 F2 F3 F4 F5 F6 F7 D W". Fi (1 <= i <= 7) is 1 or 0, representing whether the film can be made on the i-th day in a week (a week starts on Sunday): 1 means that the film can be made on this day, while 0 means the opposite. Both D (1 <= D <= 50) and W (1 <= W <= 50) are integers, and Alice should go to the film for D days and the film must be finished in W weeks.

Output

For each test case print a single line, 'Yes' if Alice can attend all the films, otherwise 'No'.

Sample Input

```2
2
0 1 0 1 0 1 0 9 3
0 1 1 1 0 0 0 6 4
2
0 1 0 1 0 1 0 9 4
0 1 1 1 0 0 0 6 2
```

Sample Output

```Yes
No
```

Hint

```A proper schedule for the first test case:

date     Sun    Mon    Tue    Wed    Thu    Fri    Sat

week1          film1  film2  film1         film1

week2          film1  film2  film1         film1

week3          film1  film2  film1         film1

week4          film2  film2  film2```

Source

POJ Monthly--2004.07.18

## Code: Edmonds-Karp, O(TVE2) [488K, 125MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int T, N, F[8], D, W, sumD;

struct Edge{
int st, np, flow, cap;
Edge *nxt, *rev;
};

struct Graph{
Edge *V[375], E[20002];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, int cap){
E[++tope].st = u, E[tope].np = v, E[tope].flow = 0, E[tope].cap = cap;
E[tope].nxt = V[u], E[tope].rev = &E[tope + 1], V[u] = &E[tope];
E[++tope].st = v, E[tope].np = u, E[tope].flow = 0, E[tope].cap = 0;
E[tope].nxt = V[v], E[tope].rev = &E[tope - 1], V[v] = &E[tope];
}
} G;  // V[0] is source, V[1..20] are movies, V[21..370] are days, and V[371] is sink.

struct Queue{
#define inc(x) (x) = ((x) < 374 ? (x) + 1 : (x) - 374)
int node[375];
int fr, re;

inline void clear() {fr = re = 0;}

inline bool empty() {return fr == re;}

inline void push(const int &x) {node[re] = x, inc(re);}

inline void pop() {inc(fr);}

inline int front() {return node[fr];}
} q;

Edge *prev[375];

inline int Edmonds_Karp(const Graph &G, int S, int T){
int maxflow = 0;
do{
q.clear(), q.push(S);
memset(prev, 0, sizeof(prev));
while(!q.empty()){
int u = q.front(); q.pop();
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(prev[ne->np] == NULL && ne->np != S && ne->cap > ne->flow)
prev[ne->np] = ne, q.push(ne->np);
}
if(prev[T]){
int dflow = 0x3f3f3f3f;
for(register Edge *ne = prev[T]; ne; ne = prev[ne->st])
dflow = min(dflow, ne->cap - ne->flow);
for(register Edge *ne = prev[T]; ne; ne = prev[ne->st])
ne->flow += dflow, ne->rev->flow -= dflow;
maxflow += dflow;
}
} while(prev[T]);
return maxflow;
}

int main(){
scanf("%d", &T);
while(T--){
G.clear();
for(register int i = 21; i <= 370; i++)
G.addedge(i, 371, 1);  // Every day Alice can attend one film at most
scanf("%d", &N);
sumD = 0;
for(register int i = 1; i <= N; i++){
for(register int j = 0; j < 7; j++) scanf("%d", F + j);
scanf("%d%d", &D, &W);
sumD += D;
G.addedge(0, i, D);  // Alice should go to the film for D days
for(register int j = 0; j < 7; j++)
if(F[j] > 0)
for(register int k = 0; k < W; k++)
G.addedge(i, k * 7 + j + 21, 1);  // Alice can attend the film on those days
}
int maxflow = Edmonds_Karp(G, 0, 371);
if(maxflow == sumD) puts("Yes");
else puts("No");
}
return 0;
}
```

## Code: Dinic, O(TV2E) [428K, 32MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define SOURCE 0
#define SINK 371
using namespace std;

int T, N, F[8], D, W, sumD;

struct Edge{
int np, flow, cap;
Edge *nxt, *rev;
};

struct Graph{
Edge *V[375], E[20002];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, int cap){
E[++tope].np = v, E[tope].flow = 0, E[tope].cap = cap;
E[tope].nxt = V[u], E[tope].rev = &E[tope + 1], V[u] = &E[tope];
E[++tope].np = u, E[tope].flow = 0, E[tope].cap = 0;
E[tope].nxt = V[v], E[tope].rev = &E[tope - 1], V[v] = &E[tope];
}
} G;  // V[0] is source, V[1..20] are movies, V[21..370] are days, and V[371] is sink.

struct Queue{
#define inc(x) (x) = ((x) < 374 ? (x) + 1 : (x) - 374)
int node[375];
int fr, re;

inline void clear() {fr = re = 0;}

inline bool empty() {return fr == re;}

inline void push(const int &x) {node[re] = x, inc(re);}

inline void pop() {inc(fr);}

inline int front() {return node[fr];}
} q;

int lev[375];
Edge *arc[375];

inline bool Dinic_BFS(){
q.clear(), q.push(SOURCE);
memset(lev, -1, sizeof(lev)), lev[SOURCE] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(ne->cap > ne->flow && lev[ne->np] == -1){
lev[ne->np] = lev[u] + 1;
q.push(ne->np);
}
}
return lev[SINK] > -1;  // The sink point must be reachable
}

inline int Dinic_DFS(int u, int curflow){
if(u == SINK) return curflow;
for(register Edge *ne = arc[u]; ne; ne = ne->nxt){
arc[u] = ne;
if(lev[ne->np] == lev[u] + 1 && ne->cap > ne->flow){  // Only next level can be augmented
int flow = Dinic_DFS(ne->np, min(curflow, ne->cap - ne->flow));
if(flow){
ne->flow += flow, ne->rev->flow -= flow;
return flow;
}
}
}
return 0;  // No more Augmenting Path
}

inline int Dinic(){
int maxflow = 0;
while(Dinic_BFS()){
int flow;
for(register int i = 0; i <= 371; i++) arc[i] = G.V[i];  // Initialize Current Arcs
while(flow = Dinic_DFS(SOURCE, 0x3f3f3f3f))
maxflow += flow;  // After each BFS we can find several Augmenting Paths by DFS
}
return maxflow;
}

int main(){
scanf("%d", &T);
while(T--){
G.clear();
for(register int i = 21; i <= 370; i++)
G.addedge(i, 371, 1);  // Every day Alice can attend one film at most
scanf("%d", &N);
sumD = 0;
for(register int i = 1; i <= N; i++){
for(register int j = 0; j < 7; j++) scanf("%d", F + j);
scanf("%d%d", &D, &W);
sumD += D;
G.addedge(0, i, D);  // Alice should go to the film for D days
for(register int j = 0; j < 7; j++)
if(F[j] > 0)
for(register int k = 0; k < W; k++)
G.addedge(i, k * 7 + j + 21, 1);  // Alice can attend the film on those days
}
int maxflow = Dinic();
if(maxflow == sumD) puts("Yes");
else puts("No");
}
return 0;
}
```

## Code: ISAP, O(TV2E) [488K, 0MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define SOURCE 0
#define SINK 371
using namespace std;

int T, N, F[8], D, W, sumD;

struct Edge{
int st, np, flow, cap;
Edge *nxt, *rev;
};

struct Graph{
Edge *V[375], E[20002];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, int cap){
E[++tope].st = u, E[tope].np = v, E[tope].flow = 0, E[tope].cap = cap;
E[tope].nxt = V[u], E[tope].rev = &E[tope + 1], V[u] = &E[tope];
E[++tope].st = v, E[tope].np = u, E[tope].flow = 0, E[tope].cap = 0;
E[tope].nxt = V[v], E[tope].rev = &E[tope - 1], V[v] = &E[tope];
}
} G;  // V[0] is source, V[1..20] are movies, V[21..370] are days, and V[371] is sink.

struct Queue{
#define inc(x) (x) = ((x) < 374 ? (x) + 1 : (x) - 374)
int node[375];
int fr, re;

inline void clear() {fr = re = 0;}

inline bool empty() {return fr == re;}

inline void push(const int &x) {node[re] = x, inc(re);}

inline void pop() {inc(fr);}

inline int front() {return node[fr];}
} q;

int dis[375];  // The distance from each point to the sink point
int num[375];  // The number of each distance
Edge *prev[375], *arc[375];

inline void ISAP_BFS(){
memset(dis, 0, sizeof(dis));
q.clear(), q.push(SINK);
while(!q.empty()){
int u = q.front(); q.pop();
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(!dis[ne->np] && ne->np != SINK) dis[ne->np] = dis[u] + 1, q.push(ne->np);
}
}

inline int ISAP(){
int maxflow = 0;
ISAP_BFS();
memset(num, 0, sizeof(num));
for(register int i = 0; i <= 371; i++) num[dis[i]]++;
memset(arc, 0, sizeof(arc));
for(register int i = 0; i <= 371; i++) arc[i] = G.V[i];
int u = SOURCE;
while(dis[SOURCE] < 372){
if(u == SINK){
int flow = 0x3f3f3f3f;
for(register Edge *ne = prev[u]; ne; ne = prev[ne->st])
flow = min(flow, ne->cap - ne->flow);
for(register Edge *ne = prev[u]; ne; ne = prev[ne->st])
ne->flow += flow, ne->rev->flow -= flow;
maxflow += flow;
u = SOURCE;  // Try to find another Augmenting Path
}
bool retreat = 1;
for(register Edge *ne = arc[u]; ne; ne = ne->nxt)
if(dis[u] == dis[ne->np] + 1 && ne->cap > ne->flow){
retreat = 0;
arc[u] = prev[ne->np] = ne;
u = ne->np;
break;
}
if(retreat){
int newid = 371;
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(ne->cap > ne->flow) newid = min(newid, dis[ne->np]);
if(--num[dis[u]] == 0) break;  // Gap optimization
num[dis[u] = newid + 1]++;
arc[u] = G.V[u];
if(u != SOURCE) u = prev[u]->st;  // Backdate
}
}
return maxflow;
}

int main(){
scanf("%d", &T);
while(T--){
G.clear();
for(register int i = 21; i <= 370; i++)
G.addedge(i, 371, 1);  // Every day Alice can attend one film at most
scanf("%d", &N);
sumD = 0;
for(register int i = 1; i <= N; i++){
for(register int j = 0; j < 7; j++) scanf("%d", F + j);
scanf("%d%d", &D, &W);
sumD += D;
G.addedge(0, i, D);  // Alice should go to the film for D days
for(register int j = 0; j < 7; j++)
if(F[j] > 0)
for(register int k = 0; k < W; k++)
G.addedge(i, k * 7 + j + 21, 1);  // Alice can attend the film on those days
}
int maxflow = ISAP();
if(maxflow == sumD) puts("Yes");
else puts("No");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai