1246-Concert Hall Scheduling

問題概要

2つの同一のコンサートホールを運営することになった．
[i,j]日の間コンサートホールを借りるのにw円支払うという情報が与えられるので，利益が最大になるようにせよ

解法

最小費用流．DPでも解けるらしい．

実装(C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int V_MAX=400;
const int INF=99999999;
struct Edge{
	int dst,weight,capacity,rev;
};
int V;
vector<Edge> G[V_MAX];
void add_edge(int s,int d,int c,int f){
	G[s].push_back((Edge){d,c,f,G[d].size()});
	G[d].push_back((Edge){s,-c,0,G[s].size()-1});
}
//最小費用流
int min_cost_flow(int src,int dst,int flow){
	int res=0;
	while(flow>0){
		vector<int> dist(V,INF);
		vector<int> backv(V,INF);
		vector<int> backe(V,INF);
		bool update=true;
		dist[src]=0;
		while(update){
			update=false;
			for(int i=0;i<V;i++){
				if(dist[i]<INF){
					for(int j=0;j<(int)G[i].size();j++){
						Edge &e=G[i][j];
						if(e.capacity==0)continue;
						if(dist[e.dst]>dist[i]+e.weight){
							dist[e.dst]=dist[i]+e.weight;
							backv[e.dst]=i;
							backe[e.dst]=j;
							update=true;
						}
					}
				}
			}
		}
		if(dist[dst]==INF){
			return -1;
		}
		//出来るだけ流す
		int f=flow;
		int now=dst;
		while(now!=src){
			f=min(f,G[backv[now]][backe[now]].capacity);
			now=backv[now];
		}
		//f流せるはずなので流してみる
		now=dst;
		while(now!=src){
			res+=G[backv[now]][backe[now]].weight*f;
			G[backv[now]][backe[now]].capacity-=f;
			G[now][G[backv[now]][backe[now]].rev].capacity+=f;
			now=backv[now];
		}
		flow-=f;
	}
	return res;
}
void init(){
	for(int i=0;i<V_MAX;i++)G[i].clear();
}
int main() {
	int n;
	while(cin>>n,n){
		V=366;
		init();
		for(int i=0;i<n;i++){
			int a,b,w;
			cin>>a>>b>>w;
			a--;
			add_edge(a,b,-w,1);
		}
		for(int i=0;i<365;i++){
			add_edge(i,i+1,0,2);
		}
		cout<<-min_cost_flow(0,365,2)<<endl;
	}
	return 0;
}