Submission #26084176

---

Source Code Expand

#include <bits/stdc++.h>
const int N = 605, M = N * 10;

int n, m, a[N], b[N], h[N], cur[N], lev[N], ans;

struct edge {
	int v, nxt, w;
} e[M];
int cnt = -1, S, T;
void add(int u, int v, int w) {
	e[++cnt] = (edge){v, h[u], w}; h[u] = cnt;
	e[++cnt] = (edge){u, h[v], 0}; h[v] = cnt;
}

int que[N], hd, tl;

bool bfs() {	 
	memset(lev, 0, sizeof(lev));
	hd = tl = lev[S] = 1; que[1] = S;
	while(hd <= tl) {
		int u = que[hd++];
		for(int i = h[u]; ~i; i = e[i].nxt) {
			int v = e[i].v;
			if(!lev[v] && e[i].w > 0) {
				que[++tl] = v;
				lev[v] = lev[u] + 1;
			}
		}
	}
	return lev[T];
}

int dfs(int u, int can_flow) {
	if(u == T) return can_flow;
	int res_flow = 0;
	for(int &i = cur[u]; ~i; i = e[i].nxt) {
		int v = e[i].v;
		if(lev[v] == lev[u] + 1 && e[i].w > 0) {
			int will_flow = dfs(v, std::min(can_flow, e[i].w));
			res_flow += will_flow;
			can_flow -= will_flow;
			e[i ^ 1].w += will_flow;
			e[i].w -= will_flow;
			if(!can_flow) break;
		}
	}
	if(!res_flow) lev[u] = 0;
	return res_flow;
}

int dinic() {
	int res = 0; 
	while(bfs()) {
		memcpy(cur, h, sizeof(h));
		res += dfs(S, INT_MAX);
	}
	return res;
}

int main() {
	memset(h, -1, sizeof(h));
	scanf("%d %d", &n, &m);
	S = n * 2 + 1; T = n * 2 + 2;
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
	for(int i = 1; i <= m; i++) {
		int u, v; scanf("%d %d", &u, &v);
		add(u + n, v, INT_MAX); add(v + n, u, INT_MAX);
	}
	for(int i = 1; i <= n; i++) add(i, i + n, a[i] + abs(b[i]));
	for(int i = 1; i <= n; i++) {
		if(b[i] >= 0) {
			add(i + n, T, 2 * b[i]);
			ans += b[i];
		} else {
			add(S, i, -2 * b[i]);
			ans -= b[i];
		}
	}
	printf("%d\n", ans - dinic());
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:62:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
./Main.cpp:64:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   64 |  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
      |                              ~~~~~^~~~~~~~~~~~~
./Main.cpp:65:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   65 |  for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
      |                              ~~~~~^~~~~~~~~~~~~
./Main.cpp:67:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   67 |   int u, v; scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Judge Result