New Equipments

思路

數據已經有提示了$b?b<=4?a?c$，這意味著，每一個$a,b,c$構成的二元一次方程只與$x$坐標最多相交一次，所以我們對每一個$a?i?i+b?i+c=y$，在$x$坐標上對應的$i$，只有唯一最值，因此我們只要對每一個方程，在它的對稱軸兩側選點即可。

問題是如何來維護這個最大值呢，顯然的每一個方程只能對應一個$x$軸上的點，這就有點像二分圖了，這里無非就是加一個$cost$邊權值嘛，所以我們只要建一個帶權的二分圖匹配，跑一個最小費用最大流不就行了。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N1 = 2e5 + 10, N2 = 2e5 + 10; const int INF = 0x3f3f3f3f;int head[N1], to[N2], nex[N2], cap[N2], cnt; ll value[N2], a[N1], b[N1], c[N1], dis[N1];int pre[N1], id[N1], flow[N1], visit[N1], n, m, s, t;void add(int x, int y, int f, ll w) {to[cnt] = y;nex[cnt] = head[x];value[cnt] = w;cap[cnt] = f;head[x] = cnt++; }bool spfa() {memset(visit, 0, sizeof visit);memset(dis, 0x3f, sizeof dis);queue<int> q;q.push(s);dis[s] = 0, visit[s] = 1, flow[s] = INF, pre[t] = -1;while(!q.empty()) {int temp = q.front();q.pop();visit[temp] = 0;for(int i = head[temp]; ~i; i = nex[i]) {if(cap[i] > 0 && dis[to[i]] > dis[temp] + value[i]) {dis[to[i]] = dis[temp] + value[i];flow[to[i]] = min(flow[temp], cap[i]);pre[to[i]] = temp;id[to[i]] = i;if(!visit[to[i]]) {q.push(to[i]);visit[to[i]] = 1;}}}}return pre[t] != -1; }int min_cost_and_max_flow() {vector<ll> ans;ll now = 0;while(spfa()) {now += flow[t] * dis[t];ans.push_back(now);int p = t;while(p != s) {cap[id[p]] -= flow[t];cap[id[p] ^ 1] += flow[t];p = pre[p];}}for(int i = 0; i < ans.size(); i++) {printf("%lld%c", ans[i], i + 1 == ans.size() ? '\n' : ' ');} }int point[N1], tot;void init() {memset(head, -1, sizeof head);cnt = tot = 0; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = read();for(int cas = 1; cas <= _; cas++) {init();n = read(), m = read();init();s = 0;for(int i = 1; i <= n; i++) {add(s, i, 1, 0);//源點向每個人建邊，add(i, s, 0, 0);a[i] = read(), b[i] = read(), c[i] = read();int mid = -(b[i] / (2 * a[i]));mid = max(1, mid);mid = min(mid, m);for(int j = mid, sum = 1; j >= 1 && sum <= n; j--, sum++) point[++tot] = j;for(int j = mid + 1, sum = 1; j <= m && sum <= n; j++, sum++) point[++tot] = j;}sort(point + 1, point + 1 + tot);tot = unique(point + 1, point + 1 + tot) - (point + 1);t = n + tot + 1;for(int j = 1; j <= tot; j++) {add(j + n, t, 1, 0);//機器向匯點建邊。add(t, j + n, 0, 0);}for(int i = 1; i <= n; i++) {//每個人跟機器連邊int mid = -(b[i] / (2 * a[i]));mid = max(1, mid);mid = min(mid, m);for(int j = mid, sum = 1; j >= 1 && sum <= n; j--, sum++) {add(i, (lower_bound(point + 1, point + 1 + tot, j) - point) + n, 1, a[i] * j * j + b[i] * j + c[i]);add((lower_bound(point + 1, point + 1 + tot, j) - point) + n, i, 0, -(a[i] * j * j + b[i] * j + c[i]));} for(int j = mid + 1, sum = 1; j <= m && sum <= n; j++, sum++) {add(i, (lower_bound(point + 1, point + 1 + tot, j) - point) + n, 1, a[i] * j * j + b[i] * j + c[i]);add((lower_bound(point + 1, point + 1 + tot, j) - point) + n, i, 0, -(a[i] * j * j + b[i] * j + c[i]));}}min_cost_and_max_flow();}return 0; }

總結

以上是生活随笔為你收集整理的2020杭电多校（二） New Equipments（最小费用最大流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。