Codeforces #571 Div2 F. Vus the Cossack and a Graph

まぁこれはすぐ思いついたかな。
https://codeforces.com/contest/1186/problem/F

問題

N頂点M辺の無向グラフが与えられる。
このうちceil((N+M)/2)本以上の辺を残し、各頂点の次数D[i]に対しceil(D[i]/2)以上残るようにせよ。

解法

元のグラフを、できるだけ長いいくつかのパスに分解しよう。
これはオイラーパスを求めることで取得できる。その際はできるだけ次数が奇数の点から開始しよう。

各パスについて、端から奇数番目の辺だけ残すようにすれば、約半分の辺と次数を残すことができる。

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	vector<vector<int>> ret;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	
	void dfs(int cur) {
		path.push_back(cur);
		if(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
	}
	
	void GetPath() { // 開始地点を探し、条件を満たすか判定
		int i;
		FOR(i,MV) {
			if(E[i].size()%2) {
				path.clear();
				dfs(i);
				ret.push_back(path);
			}
		}
		FOR(i,MV) if(E[i].size()) {
			path.clear();
			dfs(i);
			ret.push_back(path);
		}
		
	}

};

UndirectedEulerPath<1010000> uep;
int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		uep.add_path(x,y);
	}
	
	uep.GetPath();
	vector<pair<int,int>> V;
	FORR(v,uep.ret) {
		for(i=0;i+1<v.size();i+=2) V.push_back({v[i],v[i+1]});
		if(v.size()%2) V.push_back({v[v.size()-2],v[v.size()-1]});
	}
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v.first<<" "<<v.second<<endl;
	
}

まとめ

Div2Fの割には簡単かも。