TopCoder SRM 348 Div1 Medium RailwayTickets

問題

座席がn個ある電車がある。
m人の乗客がいて、それぞれはa[i]から乗りb[i]の駅で降りる。
電車には同時にn人以上が乗ることはできない。
（乗る駅および降りる駅では数に数えない）

乗客は、乗りたい区間全部に乗れないときは、電車に乗らない。
乗客を選び、最大で何人の乗客を乗せることができるか、求めよ。

制約条件

n≦1000
a[i],b[i]≦10000
乗客の最大数は500くらい？

方針

蟻本220pの問題Intervalsと全く同じ。

区間(a,b)に乗りたい客がいるとき、aからbに容量1,コスト-1の辺を張る。
(i,i+1)に容量∞、コスト0の辺を張る。
このときの最小費用流が、乗せられる客の最大数となる。

ソースコード

const int MAX_V=500;
typedef pair<int,int> P;
struct edge{ int to,cap,cost,rev; };
int V;
vector<edge> G[MAX_V];
int h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost){
	G[from].pb((edge){to,cap,cost,G[to].size()});
	G[to].pb((edge){from,0,-cost,G[from].size()-1});
}
int min_cost_flow(int s,int t,int f){
	int res=0;
	fill(h,h+V,0);
	while(f>0){
		priority_queue<P,vector<P>,greater<P> > q;
		fill(dist,dist+V,inf);
		dist[s]=0;
		q.push(P(0,s));
		while(!q.empty()){
			P p=q.top(); q.pop();
			int v=p.second;
			if(dist[v]<p.first)continue;
			rep(i,G[v].size()){
				edge &e=G[v][i];
				if(e.cap>0&&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;
					q.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==inf)return -1;
		rep(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;
}
class RailwayTickets {
	public:
	int minRejects(vector <string> travel, int seats) 
	{
		vi a,b;
		
		rep(i,MAX_V)G[i].clear();
		string s;
		rep(i,travel.size())s+=travel[i]+" ";
		rep(i,s.size())if(s[i]=='-')s[i]=' ';
		stringstream ss(s);
		
		int p,q;
		map<int,int> m;
		while(ss>>p>>q){
			a.pb(p), b.pb(q);
			m[p]=m[q]=0;
		}
		p=0;
		fr(i,m)i->second=p++;
		
//一応座標圧縮しておく。
		int n=a.size();
		rep(i,n)a[i]=m[a[i]], b[i]=m[b[i]];
		
		V=p+2;
		int ans=0;
		add_edge(V-2,0,seats,0);
		add_edge(p-1,V-1,seats,0);
		rep(i,p-1)add_edge(i,i+1,inf,0);
		
		rep(i,n){
			add_edge(b[i],a[i],1,1);
			add_edge(V-2,b[i],1,0);
			add_edge(a[i],V-1,1,0);
		}
		return min_cost_flow(V-2,V-1,seats+n);
	}
};