kmjp's blog

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

CSAcademy Round #61 : F. Xor the Graph

これも解けててよかったかもな…。
https://csacademy.com/contest/round-61/task/xor-the-graph/

問題

N要素M辺のグラフが与えられる。
各辺には0,1の値が振られている。

ここで、このグラフにおいてパスを選ぶ、という処理を繰り返す。
パスを選ぶと、その辺の0,1が反転する。
各辺の値を0にするには、パスをどのように選べばよいか。
パスの最小数と構成例を答えよ。

解法

連結成分毎に考える。
各頂点、1が設定された辺の接続数をカウントしよう。
オイラーパスの要領で考えると、1つのパスで接続数が奇数の頂点を2個解決できる。
言い換えると、max(1,接続数が奇数の頂点数/2)個のパスが必要となる。

後は具体的にどうパス群を生成するか。
接続数が奇数の頂点群のうち、2つを除いてペアにする。そしてペア同士を仮の辺を追加し、結んでしまおう。
この状態では残された接続数が奇数の点を始めるとオイラーパスを生成することができる。
このパスにおいて、もともと存在しなかった仮の辺を取り除くと、所望のパス群を求めることができる。

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath() {
		int fo=-1,odd=0,i,np=0;
		FOR(i,MV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		if(odd!=0 && odd!=2) return false;
		dfs(odd?fo:0);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}
};

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

UndirectedEulerPath<101000> uep;
int N,M;
int in[101010],should[101010];

set<pair<int,int>> DE;
vector<int> V[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>j;
		in[x]^=j;
		in[y]^=j;
		if(j) should[x]=1;
		uf(x,y);
		uep.add_path(x,y);
		if(j==0) uep.add_path(x,y);
	}
	for(i=1;i<=N;i++) V[uf[i]].push_back(i),should[uf[i]]+=should[i];
	
	vector<vector<int>> R;
	for(i=1;i<=N;i++) if(i==uf[i] && should[i]) {
		vector<int> odd;
		FORR(v,V[i]) if(in[v]) odd.push_back(v);
		assert(odd.size()%2==0);
		for(x=2;x<odd.size();x+=2) {
			DE.insert({odd[x],odd[x+1]});
			DE.insert({odd[x+1],odd[x]});
			uep.add_path(odd[x],odd[x+1]);
		}
		uep.path.clear();
		if(odd.size()) uep.dfs(odd[0]);
		else uep.dfs(i);
		int pre=-1;
		R.push_back(vector<int>());
		FORR(p,uep.path) {
			if(DE.count({pre,p})) {
				R.push_back(vector<int>());
			}
			pre=p;
			R.back().push_back(p);
		}
		
	}
	cout<<R.size()<<endl;
	FORR(r,R) {
		cout<<r.size();
		FORR(v,r) cout<<" "<<v;
		cout<<endl;
	}
}

まとめ

複数のオイラーパスで特定の辺をカバーしたいとき、先にいくつかの奇数次数の辺を結んでしまうというテクは役に立ちそう。