TopCoder SRM 506 Div1 Medium SlimeXGrandSlimeAuto

これは確か自力で解けた記憶が。
http://community.topcoder.com/stat?c=problem_statement&pm=11334

問題

N都市間の道路と距離がグラフの形で与えられる。
これらの都市をD都市からなるdistrict[i]の順でたどりたい。

この際、いくつかの都市には車が置いてある。
各都市の車はdistrict間の移動に各１回だけ使うことができる。
徒歩の移動速度と車の移動速度が与えらえるので、district[i]の都市を全部たどるのにかかる最短時間を求めよ。

解法

この問題は最小コストフロー問題に落とし込むことができる。

まずWarshall-Floydで各都市間の距離を求めておく。
次に、フローを以下の通りに構築する。

• スタートから末尾を除くdistrict[i]に相当する点に容量1、コスト0の辺を張る
• 各車に相当する点からゴールに容量1、コスト0の辺を張る
• 各district[i]からゴールに容量1、コストをdistrict[i]からdistrict[i+1]への徒歩移動時間の辺を張る
• 各district[i]から各車に容量1、コストをdistrict[i]から車のある位置を経由してdistrict[i+1]に移動する時間の辺を張る

上記のグラフに(D-1)のフローを流す最小コストを求めればよい。
車に対応する点からゴールへは容量1の辺しかないので、各車は最大１回しか利用できない。

class MinCostFlow {
public:
	struct edge { int to, capacity; ll cost, reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	ll dist[MV], prev_v[MV], prev_e[MV], NV;
	
	MinCostFlow() { init(MV); }
	void init(int NV=MV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap, int cost) {
		E[x].push_back((edge){y,cap,cost,E[y].size()});
		E[y].push_back((edge){x,0, -cost,E[x].size()-1}); /* rev edge */
	}
	
	int mincost(int from, int to, int flow) {
		int res=0,i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, 1LL<<50);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1LL<<50) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			
			if(dist[to]==1LL<<50) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

class SlimeXGrandSlimeAuto {
	public:
	int mat[51][51];
	int travel(vector <int> cars, vector <int> districts, vector <string> roads, int inverseWalkSpeed, int inverseDriveSpeed) {
		
		int x,y,z;
		districts.insert(districts.begin(),0);
		
		int C=cars.size(),N=roads.size(),D=districts.size();
		FOR(x,N) FOR(y,N) {
			if(roads[x][y]=='.') mat[x][y]=1000000;
			if(roads[x][y]>='0' && roads[x][y]<='9') mat[x][y]=1+roads[x][y]-'0';
			if(roads[x][y]>='a' && roads[x][y]<='z') mat[x][y]=11+roads[x][y]-'a';
			if(roads[x][y]>='A' && roads[x][y]<='Z') mat[x][y]=37+roads[x][y]-'A';
			if(x==y) mat[x][y]=0;
		}
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
		
		MinCostFlow mcf;
		FOR(y,C) {
			mcf.add_edge(200+y,1,1,0);
		}
		FOR(x,D-1) {
			mcf.add_edge(0,100+x,1,0);
			mcf.add_edge(100+x,1,1,mat[districts[x]][districts[x+1]]*inverseWalkSpeed);
			FOR(y,C) {
				mcf.add_edge(100+x,200+y,1,mat[districts[x]][cars[y]]*inverseWalkSpeed+mat[cars[y]][districts[x+1]]*inverseDriveSpeed);
			}
		}
		
		
		return mcf.mincost(0,1,D-1);
	}
}

まとめ

これはすんなりフローに落とし込めた。