首页 > 代码库 > loj6045 「雅礼集训 2017 Day8」价
loj6045 「雅礼集训 2017 Day8」价
传送门:https://loj.ac/problem/6045
【题解】
由于存在完美匹配,所以选择k个药就要选择>=k个药材,我们要求的是选择k个药正好选择k个药材。
那么定义选一种减肥药的代价为-pi+INF,选一种药材的代价为INF,这样最小割肯定是恰好选k个
那么 最后答案就是最小割 - Σ(-pi+INF) 【由于减肥药是负的所以要反过来。。。】
中间连的边要设成比inf大的。。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 600 + 10, M = 5e5 + 10; const int mod = 1e9+7, inf = 5e6, INF = 1e9; # define RG register # define ST static int n, m[N], a[N][N], p[N], S, T; int head[N], nxt[M], to[M], flow[M], tot=1; inline void add(int u, int v, int fl) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; flow[tot] = fl; } inline void adde(int u, int v, int fl) { add(u, v, fl), add(v, u, 0); } namespace MF { struct queue { int head, tail, q[M]; inline void set() { head = 1, tail = 0; } inline void push(int x) { q[++tail] = x; } inline void pop() { ++head; } inline int front() { return q[head]; } inline bool empty() { return head > tail; } }q; int c[N], cur[N]; inline bool bfs() { for (int i=1; i<=n+n+2; ++i) c[i] = -1; q.set(); q.push(S); c[S] = 1; while(!q.empty()) { int top = q.front(); q.pop(); for (int i=head[top]; i; i=nxt[i]) { if(c[to[i]] != -1 || flow[i] == 0) continue; c[to[i]] = c[top] + 1; q.push(to[i]); if(to[i] == T) return 1; } } return 0; } inline int dfs(int x, int low) { if(x == T) return low; int r = low, fl; for (int i=cur[x]; i; i=nxt[i]) { if(c[to[i]] != c[x]+1 || flow[i] == 0) continue; fl = dfs(to[i], min(r, flow[i])); flow[i] -= fl; flow[i^1] += fl; r -= fl; if(flow[i] > 0) cur[x] = i; if(!r) return low; } if(r == low) c[x] = -1; return low-r; } inline int main() { int ans = 0; while(bfs()) { for (int i=1; i<=n+n+2; ++i) cur[i] = head[i]; ans += dfs(S, INF); } return ans; } } int ans = 0; int main() { freopen("z.in", "r", stdin); freopen("z.out", "w", stdout); cin >> n; for (int i=1; i<=n; ++i) { cin >> m[i]; for (int j=1; j<=m[i]; ++j) { scanf("%d", &a[i][j]); adde(i, a[i][j] + n, INF); } } for (int i=1; i<=n; ++i) scanf("%d", p+i); S = n+n+1, T = n+n+2; for (int i=1; i<=n; ++i) adde(i+n, T, inf); for (int i=1; i<=n; ++i) adde(S, i, inf-p[i]), ans += inf-p[i]; ans = MF::main() - ans; cout << ans << endl; return 0; } /* 3 2 1 2 2 1 2 1 3 -10 20 -3 */
loj6045 「雅礼集训 2017 Day8」价
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。