[POJ 1698] Alice's Chance【网络流(EK/Dinic/ISAP)】
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,
- it will be made ONLY on some fixed days in a week, i.e., Alice can only work for the film on these days;
- Alice should work for it at least for specified number of days;
- 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
Output
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
Solution:
本题是最大网络流的模板题。
虽然这是我的第一道网络流,但我觉得建图还是具有一定的思维含量的。
可以将 N (N ≤ 20) 部电影 (顶点 1 ~ 20) 和 W (W ≤ 50) 个星期共计 7W 天 (顶点 21 ~ 370) 作为顶点,再加上超级源点 0 和超级汇点 371,构成一个最多具有 372 个顶点的网络。
从超级源点向每部电影连上一条容量为 Alice 所需要去的天数的边。
从每部电影向可以拍摄的日子连上一条容量为 1 的边,表示 Alice 可以在这些日子拍摄这部电影。
从每个日子向超级汇点连上一条容量为 1 的边,表示 Alice 每天只能去拍一部电影。
由于这是我的第一道网络流,我把 Edmonds-Karp, Dinic 和 ISAP 都写了一遍,顺便比较了一下效率差异。
这是我写的三个算法的伪代码: 网络流伪代码模板(Edmonds-Karp/Dinic/ISAP)
这是网上比较好的参考资料:
- Wikipedia Dinic: https://en.wikipedia.org/wiki/Dinic%27s_algorithm
- Dinic: https://www.cnblogs.com/LUO77/p/6115057.html
- Dinic: http://blog.csdn.net/xs18952904/article/details/76640250
- ISAP: http://www.renfei.org/blog/isap.html
- ISAP: https://www.cnblogs.com/foreverpiano/p/6913004.html
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; }
发表评论