AOJ 2251 Merry Christmas

AOJ ICPC

問題概要

n件の家がm本の道によりつながっている町がある。（直接または間接的につながっていない家もある）
この町にサンタがl個のプレゼントを配る。
サンタは最初町のどの家にも降りることができる。また、サンタが家から家に移動するのにかかる時間はその道の長さに等しい。


プレゼントのリストは、(家の番号) (時間)のリストにより与えられる。
このとき、全てのプレゼントを時間通り配るために必要なサンタの数の最小値を求めよ。

解法

「プレゼントのi番目を配り終えた後、同じサンタがプレゼントのj番目を配れるか」は、
プレゼントi番目の時間+(iを配る場所とjを配る場所の最短距離)≦プレゼントj番目の時間
が成り立つかどうか。


この関係をグラフにするとDAGになる。（ここまでは本番中に気づいたorz）
求めたいのはDAGの最小パス被覆である。これは二部グラフの最大マッチングにより求めることができるらしい。


グラフの頂点の1〜vの"始点"を左側に、1〜vの"終点"を右側に配置し、
u→vに辺があるとき、対応する"始点"のu番目と"終点"のv番目を結んだ二部グラフを考える。


サンタがv人いればグラフは完全にカバーできる。
また、このグラフの「マッチング一組」に対して必要なサンタは1人減らすことができるため、v-(二部グラフの最大マッチング)が最小パス被覆になる。


以上をコードにすればいい。

ソースコード

int n,m,l;
int d[100][100];
int t[1000],pl[1000];
vector<vi> e;

int p[2000]; bool v[2000];
bool rec(int s)
{
	if(s<0)return 1;
	fr(i,e[s])if(!v[*i])
	{
		v[*i]=1;
		if(rec(p[*i]))return p[s]=*i,p[*i]=s,1;
	}
	return 0;
}

int main()
{
	while(scanf("%d%d%d",&n,&m,&l),n)
	{
		rep(i,n)rep(j,n)d[i][j]=i==j?0:inf;
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c);
			d[a][b]=d[b][a]=c;
		}
		rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		
		rep(i,l)scanf("%d%d",pl+i,t+i);
		e.clear(); e.resize(2*l);
		rep(i,l)rep(j,l)if(i!=j&&d[pl[i]][pl[j]]<=t[j]-t[i])
		e[i].pb(j+l),e[j+l].pb(i);
		
		int ans=l;
		rep(i,2*l)p[i]=-1;
		rep(i,l)
		{
			rep(j,2*l)v[j]=0;
			if(rec(i))ans--;
		}
		printf("%d\n",ans);
	}
	return 0;
}

出典

2010 ICPC模擬地区予選問題J