ABC010 D問題 浮気予防 (部分点)

問題:
D - 浮気予防

解答:

www.slideshare.net


グラフを作成し、ある点からある点に行くまでに通る辺をどれくらいカットするか、もしくはある点にたどり着いた時コストを1増やす場合、この2つの操作をどれだけ行うかを求める。

まずは部分点のみ、人間関係の数が12個でこれをそれぞれカットするかしないかを求める→2^12→4096通り
全探索で計算が可能なため、
1.カットする人間関係をどれにするか決定
2.幅優先探索
3.仮に目的地にたどり着いてしまった場合、1で実施した数をインクリメントする。
1から3を繰り返し、min(カットした人間関係+目的地にたどり着いた数)が解答となる。

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)

int min(int a,int b){
	if(a>=b){return b;}
	else{return a;}
}

int main(){

	int n,g,e;
	int tmp1,tmp2;
	vector<int> p;
	vector<int> a;
	vector<int> b;
	queue<int>  q;

	int *flag;
	int ans=0xFFFFF;

	cin>>n>>g>>e;

	flag = new int[120];

	/*今回e>12の問題は対象としない*/
	if(e>12){
		return 0;
	}

	REP(i,g){
		cin>>tmp1;
		p.push_back(tmp1);
	}

	REP(i,e){
		cin>>tmp1>>tmp2;
		a.push_back(tmp1);
		b.push_back(tmp2);
	}

	/*ビットによる全探索を実施*/

	int bitNum;
	for(int i=0;i<(1<<e+1);i++){ //2^(e+1)回計算を実施する。
		bitNum=0;
		map< int , vector<int> > x;	
		REP(j,e){
			if( (i>>j)&0x1 )continue; //今回カット対象とする人間関係があったら幅優先探索には使用しない。
			x[a.at(j)].push_back(b.at(j));
			x[b.at(j)].push_back(a.at(j));
		}
		//人間関係をカットした回数を数えておく
		REP(j,20){
			bitNum += (i>>j)&0x1;
		}

		/*ここから幅優先探査*/
		/*目的の女の子に到達してしまった場合はそいつをログインさせない方針で幅優先探索を実施*/

		q.push(0);//スタートは高橋くんから

		REP(i,32){
			flag[i]=0;
		}
		flag[0]=1;


		while(q.size()){
			int top = q.front();
			q.pop();
			if(DEBUG)cout<<top<<endl;
			/*もしマークしてる女の子が出てきたらそいつをログインさせなくする。*/
			REP(j,g){
				if(top == p.at(j)){
					bitNum++;
				}
			}
			REP(j,x[top].size()){
				if(flag[x[top].at(j)]==0){
					q.push(x[top].at(j));
					flag[x[top].at(j)]=1;
				}
			}
		}

		//解答はカットした人間関係の数の最小値
		ans = min(ans,bitNum);
	}

	cout<<ans<<endl;

	return 0;
}