2293-Dangerous Tower

Dangerous Tower | Aizu Online Judge

解法

ある長さの辺を二度と使わないように，かつ合計の長さが出来るだけ大きくなるようにするので最小費用流を用いる．
JAGの解説のスライドが詳しい．

実装(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;
int N;
int A[1000],B[1000];
#define REP(i,x) for(int i=0;i<(int)(x);i++)

typedef long long Weight;
const Weight INF=1LL<<60;

struct Edge{
	int dst,cap;Weight cost,rev;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

//srcからdstへ向かう容量cap,コストcostの辺をグラフに追加する
void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){
	G[src].push_back((Edge){dst,cap,cost,G[dst].size()});
	G[dst].push_back((Edge){src,0,-cost,G[src].size()-1});
}

//sからtへの流量fの最小費用流を求める
//流せない場合は-1を返す
Weight min_cost_flow(Graph &G,int s,int t,int f){
	typedef pair<int,int> P;
	Weight res=0;
	int V=G.size();
	vector<Weight> h(V,0);
	vector<int> prevv(V);
	vector<int> preve(V);
	if(s==t)return 0;
	bool start=true;
	while(f>0){
		vector<Weight> dist(V,INF);
		if(start){
			bool update=true;
			dist[s]=0;
			while(update){
				update=false;
				REP(v,V){
					if(dist[v]==INF)continue;
					REP(i,G[v].size()){
						Edge &e=G[v][i];
						if(e.cap>0&&dist[e.dst]>dist[v]+e.cost){
							dist[e.dst]=dist[v]+e.cost;
							prevv[e.dst]=v;
							preve[e.dst]=i;
							update=true;
						}
					}
				}
			}
			start=0;
		}else{
			priority_queue<P,vector<P>,greater<P> > que;
			dist[s]=0;
			que.push(P(0,s));
			while(!que.empty()){
				P p=que.top();que.pop();
				int v=p.second;
				if(dist[v]<p.first)continue;
				for(int i=0;i<(int)G[v].size();i++){
					Edge &e=G[v][i];
					if(e.cap>0&&dist[e.dst]>dist[v]+e.cost+h[v]-h[e.dst]){
						dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst];
						prevv[e.dst]=v;
						preve[e.dst]=i;
						que.push(P(dist[e.dst],e.dst));
					}
				}
			}
		}
		if(dist[t]==INF){
			return res;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];

		Weight d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min<Weight>(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 main() {
	cin>>N;
	vector<int> vals;
	for(int i=0;i<N;i++){
		cin>>A[i]>>B[i];
		vals.push_back(A[i]);
		vals.push_back(B[i]);
	}
	std::sort(vals.begin(),vals.end());
	vals.erase(unique(vals.begin(),vals.end()),vals.end());
	Graph G(N+vals.size()+2);
	for(int i=0;i<vals.size();i++){
		for(int j=0;j<N;j++){
			if(A[j]==vals[i]){
				add_edge(G,i+2,vals.size()+2+j,1,-B[j]);
			}
			if(B[j]==vals[i]){
				add_edge(G,i+2,vals.size()+2+j,1,-A[j]);
			}
		}
	}
	for(int i=0;i<vals.size();i++){
		add_edge(G,0,i+2,1,0);
	}
	for(int j=0;j<N;j++){
		add_edge(G,vals.size()+2+j,1,1,0);
	}
	add_edge(G,0,1,2005,0);
	cout<<-min_cost_flow(G,0,1,N*2)<<endl;
	return 0;
}