WC simulation (1.2) T2 variable

variable

Background:

1.2 WC simulation T2

Analysis: network flow, maximum flow and minimum cut

In fact, this problem... At first glance, it's the minimum cut of network flow... As a result, my brain is full of split points in the examination room, and I'm happy that I didn't come up with a plan... Embarrassed face.

Consider that, obviously, W is to be funny. Finally, multiply it. For each variable, create a point I. obviously, the following three terms of each equation can be directly put forward for consideration together. For each answer w[i] statistics its contribution cnt[i]. For the positive and negative of cnt[i], after discussion, add 2 to one side of S à I and I à T *abs(cnt[i]), and then for an equation a * |w[x] - w[y] |, we're at x, The undirected edge of 2 * a between y indicates that if two different directions are selected, the middle edge must also be cut off, otherwise the same two are selected. Then we solve the limitation between variables. For x < y directly forces X and T to connect to the INF side, and S and y to connect to the INF side. If x < y, equivalent to the case where x = W, y = -W cannot exist, then directly X-Y connects the directed edge of INF, for X ==Y, just connect x to y to the edge of INF and y to X to the edge of INF. Then add the minimum cut of the original graph and the answer of the default value at the beginning.

Source:

```/*
created by scarlyw
*/
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>
#include <ctime>
#include <bitset>

inline char read() {
static const int IN_LEN = 1024 * 1024;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}

///*
template<class T>
inline void R(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read())
x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/

const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}

template<class T>
inline void W(T x) {
static int buf[30], cnt;
if (x == 0) write_char('0');
else {
if (x < 0) write_char('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) write_char(buf[cnt--]);
}
}

inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}

/*
template<class T>
inline void R(T &x) {
static char c;
static bool iosig;
for (c = getchar(), iosig = false; !isdigit(c); c = getchar())
if (c == '-') iosig = true;
for (x = 0; isdigit(c); c = getchar())
x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/

const int MAXN = 500 + 10;
const int INF = 1000000000;

struct node {
int to, w, rev;
node(int to = 0, int w = 0, int rev = 0)
: to(to), w(w), rev(rev) {}
} ;

int x, y, z, a, b, c, d, e, f, r, n, val, p, q, s, t, ans, data_case;
int temp[MAXN], dis[MAXN], cnt[MAXN];
std::vector<node> edge[MAXN];

inline void add_edge(int x, int y, int w) {
edge[x].push_back(node(y, w, edge[y].size()));
edge[y].push_back(node(x, 0, edge[x].size() - 1));
}

inline void build_graph() {
R(n), R(val), R(p), R(q), s = 0, t = n + 1, ans = 0;
for (int i = s; i <= t; ++i) edge[i].clear(), cnt[i] = 1;
for (int i = 1; i <= p; ++i) {
R(x), R(y), R(z), R(a), R(b), R(c), R(d), R(e), R(f);
add_edge(x, y, 2 * a), add_edge(y, x, 2 * a);
add_edge(y, z, 2 * b), add_edge(z, y, 2 * b);
add_edge(z, x, 2 * c), add_edge(x, z, 2 * c);
cnt[x] += (d - f), cnt[y] += (e - d), cnt[z] += (f - e);
}
for (int i = 1; i <= n; ++i)
(cnt[i] > 0) ? (ans -= cnt[i], add_edge(i, t, 2 * cnt[i]))
: (ans += cnt[i], add_edge(s, i, -2 * cnt[i]));
for (int i = 1; i <= q; ++i) {
R(x), R(y), R(r);
switch (r) {
case 0: add_edge(x, y, INF);
break ;
case 1: add_edge(x, y, INF), add_edge(y, x, INF);
break ;
case 2: add_edge(s, y, INF), add_edge(x, t, INF);
}
}
std::cerr << ans << '\n';
}

inline bool bfs(int s, int t) {
memset(dis, -1, sizeof(int) * (n + 5));
std::queue<int> q;
dis[s] = 0, q.push(s);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int p = 0; p < edge[cur].size(); ++p) {
node *e = &edge[cur][p];
if (dis[e->to] == -1 && e->w > 0) {
dis[e->to] = dis[cur] + 1;
if (e->to == t) return true ;
q.push(e->to);
}
}
}
return false;
}

inline int dfs(int cur, int low, int t) {
if (cur == t) return low;
int delta = 0;
for (int &p = temp[cur]; p < edge[cur].size(); ++p) {
node *e = &edge[cur][p];
if (dis[e->to] == dis[cur] + 1 && e->w > 0) {
int ret = dfs(e->to, std::min(low - delta, e->w), t);
e->w -= ret, edge[e->to][e->rev].w += ret;
if ((delta += ret) == low) break ;
}
}
return delta;
}

inline int max_flow(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
int ret;
while (memset(temp, 0, sizeof(int) * (n + 5)),
ret = dfs(s, INF, t))
ans += ret;
}
return ans;
}

inline void solve() {
build_graph();
W((long long)(ans + max_flow(s, t)) * val), write_char('\n');
}

int main() {
freopen("variable.in", "r", stdin);
freopen("variable.out", "w", stdout);
R(data_case);
while (data_case--) std::cerr << data_case << '\n', solve();
flush();
return 0;
}```

Tags: network

Posted on Sat, 02 May 2020 08:39:01 -0700 by mark_kccs