立命館合宿2012 day1 問題E School Excursion (AOJ 1088)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1088）

制約条件

n≦100
m[i]≦20
0≦xi,yi≦200000
cij≦1000
g≦10

方針

各駅を到着時刻と、IN,OUTで多重化したグラフを作る。
それぞれのINからOUTには容量1,コスト0の辺を張り、
到着時間から間に合う出発時間の電車について、対応するコスト（容量は1でよい）の辺を張る。

このようにして作ったグラフで、最小費用最大流を流せば、
それが問題で求めたい量である。

ソースコード

const int MAX_V=5000;
typedef pair<int,int> P;
struct edge{ int to,cap,cost,rev; };
int V=5000;
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});
}
pi 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 mp(f,res);
		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 mp(0,res);
}

int n,m[100],x[100][20],y[100][20],c[100][20],g;
int v[100],vy[100][20];
map<int,int> id[100];

int main(){
	while(cin>>n,n){
		rep(i,5000)G[i].clear();
		v[0]=1;
		m[0]=1;
		vy[0][0]=-1;
		int s=4998,t=4999, cur=1;
		for(int i=1;i<n;i++){
			cin>>m[i];
			rep(j,m[i])cin>>x[i][j]>>y[i][j]>>c[i][j], id[i][y[i][j]]=0;
			v[i]=0;
			fr(j,id[i])vy[i][j->second=v[i]++]=j->first;
			
			int nxt=cur+v[i-1];
			rep(j,v[i])add_edge(nxt+j,nxt+j+v[i],1,0);
			rep(j,v[i-1])rep(k,m[i])if(vy[i-1][j]<=x[i][k])
				add_edge(cur+j,nxt+id[i][y[i][k]],1,c[i][k]);
			cur+=v[i-1]+v[i];
		}
		cin>>g;
		add_edge(s,1,g,0);
		rep(i,v[n-1])add_edge(cur+i,t,g,0);
		
		pi ans=min_cost_flow(s,t,g);
		cout<<g-ans.first<<" "<<ans.second<<endl;
		
	}
	return 0;
}