Codeforces #237, C : Restore Graph

問題文

http://codeforces.com/contest/404/problem/C

問題概要

　整数 n, k と数列 d が与えられる。以下の condition を満たすグラフを一つ示せ。存在しない場合は -1 で示せ。

• 頂点数が n
• 全ての頂点について、次数は k 以下
• ある頂点 v を選んだとき、v から頂点 i への距離は

解法

　任意の頂点についてその次数を少なくしたいので、最小の辺数で構成することを考えます。このとき、構成されたグラフで辺が張られている二つの頂点 i, j について となります。これは、d の性質を満たすためには、d の値が 1 少ない頂点から 1 多い頂点への辺が絶対に必要であることと、値が等しくなる場合に辺を張るのは無駄であることから分かります。
　従って、グラフを構成する際には、d の値毎に頂点を分類しておいて、差が 1 となるような d の値をもつ頂点間に一本ずつ辺を張ればよいことになります。このとき、できるだけ次数を分散させるような処理をしておけば最適なグラフを得ることができます。具体的には、同じ次数の頂点からは、現状で次数が最も少ない頂点を選んで繋ぐようにするとよいです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
typedef vector<PII> VPII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )

#define fst first
#define snd second

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	
	int n, k;
	cin >> n >> k;

	VI ds( n );
	FOR( d, ds )
	{
		cin >> d;
	}

	if ( 2 <= count( ALL( ds ), 0 ) )
	{
		cout << -1 << endl;
		return 0;
	}

	const int maxd = *max_element( ALL( ds ) );
	if ( set<int>( ALL( ds ) ).size() != maxd + 1 )
	{
		cout << -1 << endl;
		return 0;
	}

	VVI d2vs( maxd + 1 );
	REP( i, 0, n )
	{
		d2vs[ ds[i] ].PB( i );
	}

	VPII res;
	REP( d, 0, maxd )
	{
		int v = 0;
		const VI &vs = d2vs[d];
		FOR( u, d2vs[ d + 1 ] )
		{
			res.emplace_back( vs[ v++ % vs.size() ], u );
		}
	}

	VI degs( n );
	FOR( r, res )
	{
		degs[ r.fst ]++;
		degs[ r.snd ]++;
	}

	if ( k < *max_element( ALL( degs ) ) )
	{
		cout << -1 << endl;
		return 0;
	}

	cout << res.size() << endl;
	FOR( r, res )
	{
		cout << r.fst + 1 << ' ' << r.snd + 1 << endl;
	}

	return 0;
}