SRM 583 Div1 500 TurnOnLamps

2013-06-18

03:02 |

木が与えられる。各枝に値(0or1)と重要かどうか(0or1)がついてる。
２つのノードを指定するとそれらの最短経路上の枝の値が反転する。これを最低何回やると重要な枝すべてを 1 にできるか。
2≦ノード数≦50

... 木の理論(?)とか分かんないし

全探索を考える
ノード２つを決めると、反転する枝の番号リストが決まる。このリストを long long に入れる
初期値 bS と重要ラベル bG も long longに入れる
初期値から遷移していって (bS&bG)==bG になったら終わり

目的の状態に近づかないものは探索しなくていいだろう
BFSでやってたけどあれってなってDijkstraに書き換え

被撃墜(OOF)

（あとで）

答えが 0 になるときの処理をしてなかった。もったいなし(´・ω・｀)
(もっと賢い簡潔な方法があるはずである)

↓passed in practice room

// 0 is good
ll f(ll a, ll g) {
	return POPCOUNTLL(g)-POPCOUNTLL(a&g);
}

struct p3 {
	ll po, no, cost;
	bool operator<(const p3& b) const {
		return po<b.po;
	}
};

class TurnOnLamps {
	public:
	int minimize(vector <int> R, string S, string G) {
		int N=R.size()+1;
		VI w;
		REP(i, N) REP(j, N) {
			if(i==j) continue;
			VI p0, p1;
			{
				int nid = i;
				while(nid) {
					p0.PB(nid-1);
					nid = R[nid-1];
				}
			}
			{
				int nid = j;
				while(nid) {
					p1.PB(nid-1);
					nid = R[nid-1];
				}
			}
			reverse(ALL(p0));
			reverse(ALL(p1));
			int k=0;
			while(k<p0.size() && k<p1.size() && p0[k]==p1[k]) k++;
			ll ww=0;
			RANGE(l, k, p0.size()) ww|=1LL<<p0[l];
			RANGE(l, k, p1.size()) ww|=1LL<<p1[l];
			w.PB(ww);
		}
		//cout<<w<<endl;
		ll bS = 0;
		REP(i, S.size()) if(S[i]=='1') bS|=1LL<<i;
		ll bG = 0;
		REP(i, G.size()) if(G[i]=='1') bG|=1LL<<i;
		
		if((bS & bG)==bG) return 0;     // これ!!
		
		priority_queue<p3> q;
		q.push((p3){-f(bS, bG), bS, 0});
		while(q.size()) {
			ll po = -q.top().po;
			ll no = q.top().no;
			ll cost = q.top().cost;
			q.pop();
			REP(i, w.size()) {
				ll nno = no ^ w[i];
				if((nno & bG)==bG) return cost+1;
				ll npo = f(nno, bG);
				if(npo < po) {
					q.push((p3){-npo, nno, cost+1});
				}
			}
		}
		return -1;
	}
};