今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!!
このセットは、全問題のタイトルの頭文字が 'D' というセットだった
問題概要
長さ の順列 が与えらえる。これらを並び替えて完全順列 ( なる が存在しない順列) となるようにしたい。
ある段階での順列が であるときに、 と とを swap するのに要するコストは で与えられる。
完全順列とするための最小コストを求めよ。
制約
考えたこと
順列はマッチングと思うこともできる、という視点がもろにハマる問題。
順列 を左ノードとして、 を右ノードとしたとき、
- は最終的に 番目の位置に行くのには だけのコストがかかる
ということに着目すると、重み付き二部マッチング問題となる。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // edge class (for network-flow) template<class FLOWTYPE, class COSTTYPE> struct Edge { int rev, from, to, id; FLOWTYPE cap, icap; COSTTYPE cost; Edge(int r, int f, int t, FLOWTYPE ca, COSTTYPE co, int id = -1) : rev(r), from(f), to(t), cap(ca), icap(ca), cost(co), id(id) {} friend ostream& operator << (ostream& s, const Edge& E) { if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ',' << E.cost << ')'; else return s; } }; // graph class (for network-flow) template<class FLOWTYPE, class COSTTYPE> struct Graph { vector<vector<Edge<FLOWTYPE, COSTTYPE> > > list; Graph(int n = 0) : list(n) { } void init(int n = 0) { list.clear(); list.resize(n); } void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; } inline vector<Edge<FLOWTYPE, COSTTYPE> >& operator [] (int i) { return list[i]; } inline const size_t size() const { return list.size(); } inline Edge<FLOWTYPE, COSTTYPE> &redge(const Edge<FLOWTYPE, COSTTYPE> &e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } void addedge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) { list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id)); list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, 0, -cost)); } void add_undirected_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) { list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id)); list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, cap, cost, id)); } friend ostream& operator << (ostream& s, const Graph& G) { s << endl; for (int i = 0; i < G.size(); ++i) { s << i << ":"; for (auto e : G.list[i]) s << " " << e; s << endl; } return s; } }; // min-cost flow (by primal-dual) template<class FLOWTYPE, class COSTTYPE> COSTTYPE MinCostFlow(Graph<FLOWTYPE, COSTTYPE> &G, int s, int t, FLOWTYPE f) { int n = (int)G.size(); vector<COSTTYPE> pot(n, 0), dist(n, -1); vector<int> prevv(n), preve(n); COSTTYPE res = 0; while (f > 0) { priority_queue<pair<COSTTYPE,int>, vector<pair<COSTTYPE,int> >, greater<pair<COSTTYPE,int> > > que; dist.assign(n, -1); dist[s] = 0; que.push(make_pair(0,s)); while(!que.empty()) { pair<COSTTYPE,int> p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < G[v].size(); ++i) { auto e = G[v][i]; if (e.cap > 0 && (dist[e.to] < 0 || dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to])) { dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(make_pair(dist[e.to], e.to)); } } } if (dist[t] < 0) return -1; for (int v = 0; v < n; ++v) pot[v] += dist[v]; FLOWTYPE d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += pot[t] * d; for (int v = t; v != s; v = prevv[v]) { Edge<FLOWTYPE,COSTTYPE> &e = G[prevv[v]][preve[v]]; Edge<FLOWTYPE,COSTTYPE> &re = G.redge(e); e.cap -= d; re.cap += d; } } return res; } int main() { int N; cin >> N; vector<int> p(N); for (int i = 0; i < N; ++i) cin >> p[i], --p[i]; Graph<int, long long> G(N*2+2); int s = N*2, t = N*2+1; for (int i = 0; i < N; ++i) { G.addedge(s, i, 1, 0); G.addedge(i+N, t, 1, 0); } for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (p[i] == j) continue; G.addedge(i, j+N, 1, (p[i]+1)*abs(i-j)); } } auto res = MinCostFlow(G, s, t, N); cout << res << endl; }