JOI2011春合宿Day1 ジョイッター(Joitter)

バグに悩んでいた時、場合分け(？)が足りないというヒントを教えてもらい解けました。最初の印象よりよっぽどつらかったです。

問題

http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf

ジャッジ

Welcome to 2011年 日本情報オリンピック春合宿OJ - 2011年 日本情報オリンピック春合宿OJ | AtCoder

解法

場合分けします。

公開設定が(1)の人がいる場合は遠慮は要りません。
公開設定が(1)である各人間から全員に繋ぐしかないです。
またその時、(2)と(3)の条件も満たされます。

それ以外で、公開設定が(2)の人がいる場合について考えます。(一番厄介)
上の場合を参考にして、ある1人から全員に繋いでしまえば公開設定(2)の人の条件も満たし、辺の数がN-1で最小です。
まずこれが辺の数を最小にする繋ぎ方です。

さて、実はまだ他の木の作り方があります。
公開設定が(2)の2つの頂点が直接繋がれていて隣の場合を考えます。(2つ離れると前述のケースになるしかない)
この時、2つの頂点のどちらからも長さ1つ分の辺を伸ばすことができるので、他の頂点はどちらかの頂点を選んで繋ぐことができます。

最後は公開設定が(3)の奴しかいない場合ですが、これは最小全域木を作ればOKです。

一番やばいのでもです。

実装

クラスカル法がどうしても好きです。

using namespace std;

#define int long long

const int MAX_N = 1000;

struct Edge
{
	int v, u, cost;

	Edge() {}
	Edge(int _v, int _u, int _cost)
	{
		v = _v; u = _u; cost = _cost;
	}

	bool operator < (const Edge &a) const
	{
		return cost < a.cost;
	}
};

struct UnionFind
{
	int par[MAX_N], rank_[MAX_N];

	UnionFind(int n)
	{
		for (int i = 0; i < n; i++)
		{
			par[i] = i;
			rank_[i] = 0;
		}
	}

	int Find(int x)
	{
		if (par[x] == x) return x;
		return par[x] = Find(par[x]);
	}
	bool Unite(int _a, int _b)
	{
		int a = Find(_a), b = Find(_b);
		if (a == b) return false;
		if (rank_[a] >= rank_[b])
		{
			par[b] = a;
			if (rank_[a] == rank_[b]) rank_[a]++;
		} else par[a] = b;
		return true;
	}
};

int N, S[MAX_N], C[MAX_N][MAX_N];

pair<int, int> Solve1()
{
	pair<int, int> res(0, 0);
	for (int i = 0; i < N; i++)
	{
		if (S[i] != 0) continue;
		for (int j = 0; j < N; j++)
		{
			if (C[i][j] == 0) continue;
			res.first++;
			res.second += C[i][j];
			C[i][j] = C[j][i] = 0;
		}
	}
	return res;
}

pair<int, int> Solve2()
{
	int mi = LLONG_MAX/2;
	for (int i = 0; i < N; i++)
	{
		int cost = 0;
		for (int j = 0; j < N; j++)
		{
			cost += C[i][j];
		}
		mi = min(mi, cost);
	}
	return make_pair(N - 1, mi);
}

pair<int, int> Solve3()
{
	int a, b = 0;
	for (int i = 0; i < N; i++)
	{
		if (S[i] == 1) a = b, b = i;
	}
	int cost = C[a][b];
	for (int i = 0; i < N; i++)
	{
		if (i == a || i == b) continue;
		cost += min(C[i][a], C[i][b]);
	}
	return make_pair(N - 1, cost);
}

pair<int, int> Solve4()
{
	vector<Edge> edges;
	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			edges.push_back(Edge(i, j, C[i][j]));
		}
	}
	sort(edges.begin(), edges.end());

	UnionFind uf(N);
	int cost = 0;
	for (int i = 0; i < edges.size(); i++)
	{
		if (uf.Unite(edges[i].v, edges[i].u)) cost += edges[i].cost;
	}
	return make_pair(N - 1, cost);
}

signed main()
{
	cin >> N;
	int cnt[3] = {};
	for (int i = 0; i < N; i++)
	{
		cin >> S[i];
		cnt[--S[i]]++;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> C[i][j];
		}
	}
	pair<int, int> ans;
	if (cnt[0] > 0) ans = Solve1();
	else if (cnt[1] > 0)
	{
		ans = Solve2();
		if (cnt[1] == 2) ans = min(ans, Solve3());
	}
	else ans = Solve4();
	printf("%lld %lld\n", ans.first, ans.second);
	return 0;
}