ZOJ 3229 Shoot the Bullet——有源汇有上下界最大流

ZOJ 3229 Shoot the Bullet——有源汇有上下界最大流

描述：文文要给幻想乡中的m个人拍照，每天要对给定的C个人拍照（比如要给灵梦、魔理沙、紫adsfas拍照），每天拍照总数不能超过D[i]张，并且每天给每个人的拍照数要在【L, R】内，经过n天的拍照后，给每个人的拍照总数不能少于G[i],否则文文就会遭到大家终符的攻击。在上面的限制下问文文最多能拍多少张照片，并且输出每天分别给这天指定的C个人拍的照片数，如果文文无法避免终符的攻击，输出-1

思路：裸的有源汇有上下界最大流，

#include #include #include #include #include #include using namespace std;const int maxn = 2000;const int maxm = 4e5;const int INF = 0x3f3f3f3f;struct Edge { int from, to, flow, cap, up, down;};struct Dinic { vector edges; vector G[maxn]; int level[maxn], cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from, int to, int cap, int up, int down) { edges.push_back(Edge{from, to, 0, cap, up, down}); edges.push_back(Edge{to, from, 0, 0, up, down}); G[from].push_back(edges.size()-2); G[to].push_back(edges.size()-1); } int bfs(int s, int t) { memset(level, 0, sizeof(level)); level[s] = 1; queue q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap - e.flow > 0 && !level[e.to]) { level[e.to] = level[u] + 1; q.push(e.to); } } } return level[t]; } int dfs(int u, int f, int t) { if (u == t || !f) return f; for (int &i = cur[u]; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap - e.flow > 0 && level[e.to] == level[u] + 1) { int d = dfs(e.to, min(f, e.cap - e.flow), t); if (d > 0) { e.flow += d; edges[G[u][i]^1].flow -= d; return d; } } } return 0; } int maxflow(int s, int t) { int ans = 0, f; while (bfs(s, t)) { memset(cur, 0, sizeof(cur)); while ((f = dfs(s, INF, t))) ans += f; } return ans; }}ac1, ac2;int G[maxn], D[maxn], A[maxn], F[maxm];int main() { int n, m; while (~scanf("%d%d", &n, &m)) { ac1.init(); memset(A, 0, sizeof(A)); int s = n+m, t = n+m+1, ss = n+m+2, tt = n+m+3; for (int i = 0; i < m; i++) scanf("%d", &G[i]); int C, sumc = 0; for (int i = 0; i < n; i++) { int t, l, r; scanf("%d%d", &C, &D[i]); sumc += C; for (int j = 0; j < C; j++) { scanf("%d%d%d", &t, &l, &r); ac1.addedge(i, t+n, r - l, r, l); A[i] -= l; A[t+n] += l; } } for (int i = 0; i < n; i++) { ac1.addedge(s, i, D[i], D[i], 0); A[s] -= 0; A[i] += 0; } for (int i = 0; i < m; i++) { ac1.addedge(i+n, t, INF, INF, G[i]); A[i+n] -= G[i]; A[t] += G[i]; } ac1.addedge(t, s, INF, INF, 0); A[t] -= 0; A[s] += 0; int sum = 0; for (int i = 0; i <= n+m+1; i++) { if (A[i] < 0) { ac1.addedge(i, tt, -A[i], INF, 0); sum -= A[i]; } else { ac1.addedge(ss, i, A[i], INF, 0); } } int maxf = ac1.maxflow(ss, tt); if (sum == maxf) { int len = (n+m+sumc)*2; int ans1 = ac1.edges[len].flow; ac2.init(); int cnt = 0; for (int i = 0; i < len; i += 2) { int u = ac1.edges[i].from, v = ac1.edges[i].to, cap = ac1.edges[i].cap - ac1.edges[i].flow; if (cnt < sumc) { F[cnt++] = ac1.edges[i].flow + ac1.edges[i].down; } ac2.addedge(u, v, cap, INF, 0); } int ans2 = ac2.maxflow(s, t); printf("%d\n", ans1 + ans2); for (int i = 0, j = 0; j < sumc; i += 2, j++) { printf("%d\n", ac2.edges[i].flow + F[j]); } } else { printf("-1\n"); } printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。