OUPC2012 問題C Divisor (AOJ2352)

問題

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

制約条件

x≦100
xi≦10^8
xiは互いに異なる

方針

xi | xjのときにjからiへの辺を張るようなグラフを作ると、DAGの推移閉包をとったグラフになる。
求めたいのはDAGの推移閉包をとったグラフ上でどの二つも弱連結でないような頂点の集合の要素の最大数。

これは、最小パス被覆の個数に等しい（Dilworthの定理）
したがって、二部グラフの最大マッチングを使って、最小パス被覆の個数を求めてやればよい。

あとは、辞書順で最小のものをどう求めるかであるが、
これは先頭から1要素ずつ、使ったことにして、その度にマッチングを求め、答えが減らないかどうかを見て、使えるかを決定していけばいい。

ソースコード

int m,p[200];
bool v[200],e[200][200];
bool match(int s){
	if(s<0)return 1;
	rep(i,2*m)if(!v[i]&&e[s][i]){
		v[i]=1;
		if(match(p[i]))return p[i]=s,p[s]=i,1;
	}
	return 0;
}
int calc(vi &x){
	m=x.size();
	rep(i,2*m)rep(j,2*m)e[i][j]=0;
	rep(i,2*m)p[i]=-1;
	rep(i,m)rep(j,m)e[i][j+m]=e[j+m][i]=i!=j&&x[i]%x[j]==0;
	
	int res=m;
	rep(i,m)if(p[i]<0){
		rep(j,2*m)v[j]=0;
		if(match(i))res--;
	}
	return res;
}
int ans,sz,a[100];
void solve(vi &x){
	if(x.empty())return;
	vi nxt;
	rep(i,x.size()-1){
		if(x[i+1]%x[0]==0||x[0]%x[i+1]==0)continue;
		nxt.pb(x[i+1]);
	}
	if(calc(nxt)==ans-sz-1){
		a[sz++]=x[0];
		solve(nxt);
	}
	else{
		x.erase(x.begin());
		solve(x);
	}
}

int main(){
	int n; cin>>n;
	vi x(n);
	map<int,int> idx;
	rep(i,n)cin>>x[i],idx[x[i]]=i+1;
	ans=calc(x);
	
	solve(x);
	rep(i,sz)cout<<idx[a[i]]<<(i==sz-1?"\n":" ");
	
	return 0;
}