実装
各値には1からid-1までの番号が付く
始点: 0
Xの各頂点: 1〜id-1
Yの各頂点: id〜n-1
終点: id+n
という対応
const int MAXV = 4040;
class MCF {
private:
struct edge {int to, cap, cost, rev;};
vector<edge> g[MAXV];
int V, h[MAXV], dist[MAXV], prevv[MAXV], preve[MAXV];
public:
void add_edge(int from, int to, int cap, int cost) {
g[from].push_back((edge){to, cap, cost, (int)g[to].size()});
g[to].push_back((edge){from, 0, -cost, (int)g[from].size()-1});
}
int getflow(int s, int t, int f, int n) {
V = n;
int res = 0;
fill(h, h+V, 0);
if (0<f) {
fill(h, h+V, 1<<30);
h[s] = 0;
while (1) {
bool upd = 0;
for (int i=0; i<V; i++) for (auto &e : g[i]) if (e.cap) {
if (h[i]==(1<<30)) continue;
if (h[e.to] > h[i]+e.cost) {
h[e.to] = h[i] + e.cost;
upd = 1;
}
}
if (!upd) break;
}
}
while (0<f) {
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
fill(dist, dist+V, 1<<30);
dist[s] = 0;
que.push({0,s});
while (!que.empty()) {
pair<int,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++) {
edge &e = g[v][i];
if (0<e.cap && dist[e.to] > dist[v]+e.cost+h[v]-h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v, preve[e.to] = i;
que.push({dist[e.to], e.to});
}
}
}
if (dist[t]==(1<<30)) return -1;
for (int v=0; v<V; v++) h[v] += dist[v];
int d = f;
for (int v=t; v!=s; v=prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
f -= d;
res += d*h[t];
for (int v=t; v!=s; v=prevv[v]) {
edge &e = g[prevv[v]][preve[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return res;
}
};
int n, a[1010], b[1010], id = 1;
map<int,int> m;
MCF mcf;
signed main() {
cin >> n;
rep(i,n) {
cin >> a[i] >> b[i];
if (!m[a[i]]) m[a[i]] = id++;
if (!m[b[i]]) m[b[i]] = id++;
}
reps(i,1,id) mcf.add_edge(0,i,1,0);
rep(i,n) {
mcf.add_edge(m[a[i]],id+i,1,-b[i]);
mcf.add_edge(m[b[i]],id+i,1,-a[i]);
mcf.add_edge(id+i,id+n,1,0);
}
mcf.add_edge(0,id+n,n,0);
cout << -mcf.getflow(0,id+n,n,id+n+1) << endl;
}
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2293&lang=jp
