[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=2127
[算法]
首先默认每个人都选文科
那么 , "选"就是指选理科 , 而"不选"就是指选文科
那么选所获得的收益就是(V理 - V文)
而额外获得的收益可以看作是 : 若两个点同时选 , 可以获得一些收益和若两个点中有一个不选 , 则会失去收益
解最大权闭合子图 , 即可
时间复杂度 : O(dinic(N,M))
[代码]
#include<bits/stdc++.h> using namespace std; #define N 110 typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int inf = 2e9; struct edge { int to , w , nxt; } e[N * N * 50]; int total , tot , S , T , n , m; int head[N * N * 5] , dep[N * N * 5] , a[N][N] , b[N][N] , point[N][N]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘; x *= f; } inline void addedge(int u , int v , int w) { ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot; ++tot; e[tot] = (edge){u , 0 , head[v]}; head[v] = tot; } inline bool bfs() { queue< int > q; for (int i = 1; i <= total; i++) dep[i] = -1; dep[T] = -1; q.push(S); dep[S] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (w > 0 && dep[v] == -1) { dep[v] = dep[cur] + 1; q.push(v); if (v == T) return true; } } } return false; } inline int dinic(int u , int flow) { int rest = flow; if (u == T) return flow; for (int i = head[u]; i && rest; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (w > 0 && dep[v] == dep[u] + 1) { int k = dinic(v , min(rest , w)); if (!k) dep[v] = 0; rest -= k; e[i].w -= k; e[i ^ 1].w += k; } } return flow - rest; } int main() { read(n); read(m); int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { read(a[i][j]); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { read(b[i][j]); ans += b[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { point[i][j] = ++total; } } tot = 1; S = 0 , T = 5 * N * N - 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] >= b[i][j]) { ans += a[i][j] - b[i][j]; addedge(S , point[i][j] , a[i][j] - b[i][j]); } else addedge(point[i][j] , T , b[i][j] - a[i][j]); } } // NM + 4NM = 5NM // 24NM + 2NM = 26NM for (int i = 1; i < n; i++) { for (int j = 1; j <= m; j++) { int x; read(x); ans += x; ++total; addedge(S , total , x); addedge(total , point[i][j] , inf); addedge(total , point[i + 1][j] , inf); } } for (int i = 1; i < n; i++) { for (int j = 1; j <= m; j++) { int x; read(x); ans += x; ++total; addedge(total , T , x); addedge(point[i][j] , total , inf); addedge(point[i + 1][j] , total , inf); } } for (int i = 1; i <= n; i++) { for (int j = 1; j < m; j++) { int x; read(x); ans += x; ++total; addedge(S , total , x); addedge(total , point[i][j] , inf); addedge(total , point[i][j + 1] , inf); } } for (int i = 1; i <= n; i++) { for (int j = 1; j < m; j++) { int x; read(x); ans += x; ++total; addedge(total , T , x); addedge(point[i][j] , total , inf); addedge(point[i][j + 1] , total , inf); } } while (bfs()) { while (int flow = dinic(S , inf)) ans -= flow; } printf("%d\n" , ans); return 0; }