首页 > 代码库 > Alice's Chance
Alice's Chance
题目链接
- 题意:
爱丽丝要拍电影,有n部电影,规定爱丽丝第i部电影在每个礼拜只有固定的几天可以拍电影,且只能在前wi个周拍,并且这部电影要拍di天才能结束,问爱丽丝能不能拍完所有的电影
第一行代表有多少组数据,对于每组数据第一行代表有n部电影,接下来2到n+1行,每行代表一个电影,每行9个数,前面7个数,1代表拍,0代表不拍,第8个数代表要拍几天,第9个数代表有几个礼拜时间拍 - 分析:
对于每个电影,di - x[0] - x[1] - ... - x[t] = 0,di表示这个电影需要的天数,x[]表示电影对应的这些天是否选择(取值为零或一)
对于每一天,y[0] - y[1] - ... - y[t] <= 1,1表示这一天最多拍一个电影,y[]表示对应的电影是否在这一天拍(取值为零或一)
struct Edge { int from, to, cap, flow; bool operator< (const Edge& rhs) const { return from < rhs.from || (from == rhs.from && to < rhs.to); } }; const int MAXV = 500; struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[MAXV]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[MAXV]; // BFS使用 int d[MAXV]; // 从起点到i的距离 int cur[MAXV]; // 当前弧指针 int p[MAXV]; // 可增广路上的上一条弧 int num[MAXV]; // 距离标号计数 void AddEdge(int from, int to, int cap) { edges.push_back((Edge) { from, to, cap, 0 }); edges.push_back((Edge) { to, from, 0, 0 }); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(t); vis[t] = 1; d[t] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); REP(i, G[x].size()) { Edge& e = edges[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = 1; d[e.from] = d[x] + 1; Q.push(e.from); } } } return vis[s]; } void ClearAll(int n) { this->n = n; REP(i, n) G[i].clear(); edges.clear(); } void ClearFlow() { REP(i, edges.size()) edges[i].flow = 0; } int Augment() { int x = t, a = INF; while(x != s) { Edge& e = edges[p[x]]; a = min(a, e.cap-e.flow); x = edges[p[x]].from; } x = t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow -= a; x = edges[p[x]].from; } return a; } int Maxflow(int s, int t, int need) { this->s = s; this->t = t; int flow = 0; BFS(); memset(num, 0, sizeof(num)); REP(i, n) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { flow += Augment(); if(flow >= need) return flow; x = s; } int ok = 0; FF(i, cur[x], G[x].size()) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to] + 1) // Advance { ok = 1; p[e.to] = G[x][i]; cur[x] = i; // 注意 x = e.to; break; } } if(!ok) // Retreat { int m = n-1; // 初值注意 REP(i, G[x].size()) { Edge& e = edges[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m + 1]++; cur[x] = 0; // 注意 if(x != s) x = edges[p[x]].from; } } return flow; } vector<int> Mincut() // call this after maxflow { BFS(); vector<int> ans; REP(i, edges.size()) { Edge& e = edges[i]; if(!vis[e.from] && vis[e.to] && e.cap > 0) ans.push_back(i); } return ans; } void Reduce() { REP(i, edges.size()) edges[i].cap -= edges[i].flow; } void print() { printf("Graph:\n"); REP(i, edges.size()) printf("%d->%d, %d, %d\n", edges[i].from, edges[i].to , edges[i].cap, edges[i].flow); } } mf; int day[18]; int main() { int T, n, d, w; RI(T); FE(kase, 1, T) { int sum = 0; RI(n); mf.ClearAll(n + 7 * 50 + 2); int S = 0, T = n + 7 * 50 + 1, Max = -1; FE(i, 1, n) { FE(j, 1, 7) RI(day[j]); RII(d, w); sum += d; Max = max(Max, w); mf.AddEdge(S, i, d); FE(j, 1, 7) if (day[j]) { REP(k, w) mf.AddEdge(i, n + k * 7 + j, 1); } } FE(i, 1, 7) REP(j, Max) mf.AddEdge(n + j * 7 + i, T, 1); printf("%s\n", mf.Maxflow(S, T, INF) == sum ? "Yes" : "No"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。