kmjp's blog

競技プログラミング参加記です

AtCoder ARC #013 : D - 切り分けできるかな?

これ当日不参加だったこともあり解いた時期が遅く、ここに書き忘れていたので書いておく。
http://arc013.contest.atcoder.jp/tasks/arc013_4

問題

各辺の長さが整数の直方体が何通りか与えられる。
各直方体はたくさんある。

各直方体をどこかの面と平行な面で切断し、各辺の長さが整数の2つの直方体にすることを考える。
手持ちの直方体から切断により生成可能な全ての直方体"の体積"をそれぞれ2個以上そろえるには、最少で何個の直方体を切断する必要があるか。

解法

最大フローを使って解けばよい。

各体積を2個ずつ作るので、各体積に対応するグラフ上の点を2セット準備する。
最大体積は8000なので、以下では1~8000及び8001~16000と2セット作っている。

体積Vの直方体からA+Bの2つの直方体に切断できるとする(もちろん切断面の取り方によってA,Bの組み合わせは色々ある)
この時、生成しないといけない体積としてA,Bが登場するので、s→A、s→B、8000+A→t、8000+B→tの辺をグラフに追加する。
また、AとBを1回で作成できるのでA→8000+Bをグラフに追加する。


何も考えないと、各体積の直方体は元の直方体から1個ずつ切り出すため、体積候補×2だけ切断前の直方体が必要となる。
しかし切断した両側の直方体を利用できればその分必要な直方体が減るので、体積候補×2から最大フローの値を引けばよい。

int N;

set<pair<int,int> > S;
set<int> C;

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 17000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0) {
				if((tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
					e.capacity -= tf;
					E[e.to][e.reve].capacity += tf;
					return tf;
				}
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};


void addbox(int x1,int y1,int z1,int x2,int y2,int z2) {
	int v1=x1*y1*z1;
	int v2=x2*y2*z2;
	C.insert(v1);
	C.insert(v2);
	S.insert(make_pair(v1,v2));
}

void solve() {
	int f,r,i,j,k,l;
	int x,y,z,mx,my,mz;
	
	cin>>N;
	FOR(i,N) {
		cin>>mx>>my>>mz;
		for(x=1;x<mx;x++) addbox(x,my,mz,mx-x,my,mz);
		for(y=1;y<my;y++) addbox(mx,y,mz,mx,my-y,mz);
		for(z=1;z<mz;z++) addbox(mx,my,z,mx,my,mz-z);
	}
	
	MaxFlow mf;
	ITR(ci,C) {
		mf.add_edge(0,*ci,1);
		mf.add_edge(8000+*ci,16001,1);
	}
	ITR(si,S) {
		mf.add_edge(si->first,8000+si->second,1);
	}
	
	_P("%d\n",C.size()*2-mf.maxflow(0,16001));
}

まとめ

なんか2部グラフ問題も最大フローで解く癖がついてるな。