Problem B. Battlefield @ Online Competition Africa and Arabia 2011

Code Jam Africa 2011の本戦B問題

http://code.google.com/codejam/contest/dashboard?c=842485#s=p1

問題文が難しかった。ホンヤク。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

Problem B. Battlefield
You are playing a game where the battlefield consists of N cities and R bidirectional roads.
Your goal is to start at some city C of your choice and visit all R roads exactly once ending this trip at C.
If this is not possible you must add the minimum number of additional roads to the initial set of roads to make this trip feasible.
Please note that there might be more than one road connecting the same pair of cities and that you are allowed to add roads
between any pair of cities regardless of whether they already had roads connecting them or not as shown in the sample input/output.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

問題B. 戦場
N個の都市とR個の道（双方向）の戦場で遊んでいる。
目的は、ある都市Cから始めてR個の道すべてを一回だけ通ってCへ戻ってくること。
不可能なら、実行可能にするために、必要最小限の道を追加すべし。
すでに繋がっている都市間にも道路は追加できるよ。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

すぐに一筆書き絡みの問題かなという予想は付いたが、問題の正確な意味が取れず嵌まる。

さらに実装ミスでIncorrect。問題文とコードを行ったり来たり。
英語力不足で二重苦。。

1.連結都市をグループ化
2.グループ内に偶数個の道の集まる都市しかない数をカウント
3.偶数グループが2個以上なら道で数珠繋ぎにして奇数グループ化
4.全体から奇数個の道の集まる都市の数をカウント
5.奇数都市を繋ぐ道の数は奇数都市の半分
という方針。

ソース。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <list>
#include <string>
#include <sstream>

using namespace std;

struct City
{
	City():index_of_a_group(0){}

	int index_of_a_group;
	vector<City*> cities;
};

typedef vector<City> Cities;

void make_a_group(City &city, int index_of_a_group)
{
	if (0==city.index_of_a_group)
	{
		city.index_of_a_group = index_of_a_group;
	}
	else
	{
		index_of_a_group = city.index_of_a_group;
	}

	for(int i=0; i<city.cities.size(); ++i)
	{
		if (0==city.cities[i]->index_of_a_group)
		{
			city.cities[i]->index_of_a_group = index_of_a_group;
			make_a_group(*city.cities[i], index_of_a_group);
		}
	}
}

void solve_a_case(ifstream &in, int &num_of_roads_to_be_added)
{
	// input
	int num_of_cities;
	in >> num_of_cities;
	Cities cities(num_of_cities);

	int num_of_roads;
	in >> num_of_roads;

	for(int i=0; i<num_of_roads; ++i)
	{
		int a, b;
		in >> a;
		in >> b;

		cities[a].cities.push_back(&(cities[b]));
		cities[b].cities.push_back(&(cities[a]));
	}

	// grouping
	int index_of_a_group = 1;
	for(int i=0; i<num_of_cities; ++i)
	{
		make_a_group(cities[i], index_of_a_group);
		index_of_a_group++;
	}

	// cities with odd
	int num_of_cities_with_odd = 0;
	for(int i=0; i<num_of_cities; ++i)
	{
		if (1==cities[i].cities.size()%2)
		{
			num_of_cities_with_odd++;
		}
	}

	// unicursal group
	int num_of_unicursal_group = 0;
	for(int i=0; i<=index_of_a_group; ++i)
	{
		bool ok = true;
		bool ok2 = false;
		for(int j=0; j<cities.size(); ++j)
		{
			if (i==cities[j].index_of_a_group)
			{
				ok2 = true;
				if (0==cities[j].cities.size() || 1==cities[j].cities.size()%2)
				{
					ok = false;
					break;
				}
			}
		}
		if (ok && ok2)
			num_of_unicursal_group++;
	}

	// determination
	if (2<=num_of_unicursal_group)
	{
		num_of_roads_to_be_added = (num_of_cities_with_odd+2)/2+num_of_unicursal_group-1;
	}
	else if (1==num_of_unicursal_group)
	{
		if (0==num_of_cities_with_odd)
			num_of_roads_to_be_added = 0;
		else
			num_of_roads_to_be_added = num_of_cities_with_odd/2+1;
	}
	else
	{
		num_of_roads_to_be_added = num_of_cities_with_odd/2;
	}
}

void solve_all_cases(ifstream &in, ofstream &out)
{
	int case_num = 0;

	in >> case_num;
	for(int i=0; i<case_num; i++)
	{
		int r = -1;
		solve_a_case(in, r);

		out << "Case #" << i+1 << ": " << r << endl;
	}
}

int main()
{
#if 0
	ifstream in("in.txt");
	ofstream out("out.txt");
#elif 0
	ifstream in("B-small-practice.in");
	ofstream out("B-small-practice.out");
#elif 1
	ifstream in("B-large-practice.in");
	ofstream out("B-large-practice.out");
#endif

	solve_all_cases(in, out);

	return 0;
}

非常に汚いコードになってしまってるので反省。
なんとかコレクト。