1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
#define MAX_N 22 #define INF 987654321 #define EPS 1e-9 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vall3 vector<array<ll,3>> #define all5 array<ll,5> #define vall5 vector<all5> #define vll vector<ll> #define vs vector<string> #define usll unordered_set<ll> #define vvs vector<vs> #define vvll vector<vll> #define all(a) begin(a), end(a)
using namespace std;
ll n, m; ll source, sink; ll flo[MAX_N][MAX_N], cap[MAX_N][MAX_N], cost[MAX_N][MAX_N], path[MAX_N]; vll adj[MAX_N]; bool bfs(ll u, ll v) { bool inc[MAX_N]; vll w(MAX_N, INF); memset(inc, 0, sizeof inc); memset(path, 0, sizeof path); queue<ll> q; w[u] = 0; inc[u] = true; q.push(u);
while(!q.empty()) { auto n = q.front(); q.pop(); inc[n] = false; for(auto& m : adj[n]) { if(cap[n][m] - flo[n][m] > 0 and w[n] + cost[n][m] < w[m]) { w[m] = w[n] + cost[n][m]; path[m] = n; if(!inc[m]) { inc[m] = true; q.push(m); } } } }
return path[v] != 0; }
ll solve(vector<vector<int>> matrix) { for(ll i = 0; i < MAX_N; i++) adj[i].clear(); memset(flo, 0, sizeof flo); n = matrix.size(); m = matrix[0].size(); ll gap = n; source = n + m + 10; sink = source + 1; for(ll i = 1; i <= n; i++) { for(ll j = 1; j <= m; j++) { adj[i].push_back(j + gap); adj[j + gap].push_back(i);
cost[i][j + gap] = matrix[i-1][j-1]; cost[j + gap][i] = -matrix[i-1][j-1];
cap[i][j + gap] = 1; } } for(ll i = 1; i <= n; i++) { adj[source].push_back(i); adj[i].push_back(source);
cap[source][i] = 1; } for(ll j = 1; j <= m; j++) { adj[j + gap].push_back(sink); adj[sink].push_back(j + gap);
cap[j + gap][sink] = 1; } ll c = 0;
while(bfs(source, sink)) { ll v = sink, mi = INT_MAX; while(v != source) { ll u = path[v]; mi = min(mi, cap[u][v] - flo[u][v]); v = u; }
v = sink;
while(v != source) { ll u = path[v]; c += mi * cost[u][v];
flo[u][v] += mi; flo[v][u] -= mi;
v = u; } } return c; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed); cout.precision(8); cout << solve({{2500,4000,3500},{4000,6000,3500},{2000,4000,2500}});
return 0; }
|