Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- const int MAXN = 300;
- int from = MAXN * 2, to = 2 * MAXN + 1;
- const int INF = 1e9;
- vector<int> dist(2 * MAXN + 2, INF);
- vector<int> p(2 * MAXN + 2);
- vector<int> been(2 * MAXN + 2);
- struct Edge {
- int _from, _to, cost, flow, capacity;
- Edge* back_edge;
- Edge(int from, int to, int capacity, int cost) : _from(from), _to(to), capacity(capacity), cost(cost), flow(0),
- back_edge(0) {}
- inline int getCost() const {
- return cost + p[_from] - p[_to];
- }
- inline int getCapacity() const {
- return capacity - flow;
- }
- };
- vector<int> d[MAXN];
- vector<Edge*> g[5 * MAXN];
- vector<Edge*> edges;
- vector<Edge*> prevs(5 * MAXN, nullptr);
- int main() {
- cin.tie(0);
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- d[i].resize(n);
- for (int j = 0; j < n; ++j) {
- cin >> d[i][j];
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- Edge *e = new Edge(i, MAXN + j, 1, d[i][j]);
- Edge *back_edge = new Edge(MAXN + j, i, 0, -d[i][j]);
- e->back_edge = back_edge;
- back_edge->back_edge = e;
- g[i].push_back(e);
- g[MAXN + j].push_back(back_edge);
- edges.push_back(e);
- edges.push_back(back_edge);
- }
- }
- for (int i = 0; i < 2 * MAXN + 2; ++i) {
- random_shuffle(g[i].begin(), g[i].end());
- }
- for (int i = 0; i < n; ++i) {
- Edge *e = new Edge(from, i, 1, 0);
- Edge *back_edge = new Edge(i, from, 0, 0);
- e->back_edge = back_edge;
- back_edge->back_edge = e;
- g[from].push_back(e);
- g[i].push_back(back_edge);
- edges.push_back(e);
- edges.push_back(back_edge);
- }
- for (int i = 0; i < n; ++i) {
- Edge *e = new Edge(MAXN + i, to, 1, 0);
- Edge *back_edge = new Edge(to, MAXN + i, 0, 0);
- e->back_edge = back_edge;
- back_edge->back_edge = e;
- g[MAXN + i].push_back(e);
- g[to].push_back(back_edge);
- edges.push_back(e);
- edges.push_back(back_edge);
- }
- dist.assign(2 * MAXN + 2, INF);
- prevs.assign(2 * MAXN + 2, nullptr);
- dist[from] = 0;
- for (int i = 0; i < 2 * MAXN + 2; ++i) {
- for (auto x : edges) {
- if (x->getCapacity() > 0 && dist[x->_from] != INF && dist[x->_to] > dist[x->_from] + x->cost) {
- dist[x->_to] = dist[x->_from] + x->cost;
- prevs[x->_to] = x;
- }
- }
- }
- for (int i = 0; i < 2 * MAXN + 2; ++i) {
- p[i] = dist[i];
- }
- int ans = 0;
- while (dist[to] != INF) {
- int now = to;
- while (prevs[now] != nullptr) {
- prevs[now]->flow++;
- prevs[now]->back_edge->flow--;
- ans += prevs[now]->cost;
- now = prevs[now]->_from;
- }
- dist.assign(2 * MAXN + 2, INF);
- prevs.assign(2 * MAXN + 2, nullptr);
- been.assign(2 * MAXN + 2, 0);
- dist[from] = 0;
- for (int i = 0; i < 2 * MAXN + 2; ++i) {
- int v = -1;
- for (int j = 0; j < 2 * MAXN + 2; ++j)
- if (!been[j] && (v == -1 || dist[j] < dist[v]))
- v = j;
- if (dist[v] == INF)
- break;
- been[v] = true;
- for (auto e : g[v]) {
- if (e->getCapacity() > 0 && dist[v] + e->getCost() < dist[e->_to]) {
- dist[e->_to] = dist[v] + e->getCost();
- prevs[e->_to] = e;
- }
- }
- }
- for (int i = 0; i < 2 * MAXN + 2; ++i) {
- p[i] = p[i] + dist[i];
- }
- }
- cout << ans << '\n';
- for (auto x : edges) {
- if (x->_from < MAXN && x->flow > 0) {
- cout << x->_from + 1 << " " << x->_to - MAXN + 1 << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement