BUET Inter-University Programming Contest - 2011 G, UVa-12430 : Grand Wedding

問題概要

ノード数N(<5*10^4)、辺数M(<8*10^4)の重み付き無向グラフが与えられる。重みがw以上の辺を除去して二部グラフになるようにしたい。ただし全て取り除いてはならない。wとしてとれる値の最大値を求める問題。

解法

二分探索+二部グラフチェックする。

acceptされたコード

計算量O(log M * (M + N))。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = 50000;

struct edge{
	int tar;
	int64 w;
};

int N, M;
vector<edge> graph[MAX_N];
int color[MAX_N];
vector<int64> compress;

void init(){
	scanf("%d%d", &N, &M);

	for(int i=0; i<N; i++){
		graph[i].clear();
	}

	compress.clear();
	for(int i=0; i<M; i++){
		int a, b;
		int64 c;
		scanf("%d%d%lld", &a, &b, &c);
		a--; b--;
		compress.push_back(c);
		graph[a].push_back((edge){b, c});
		graph[b].push_back((edge){a, c});
	}
}

bool dfs(int v, int col, int64 x){
	color[v] = col;
	for(int i=0; i<(int)graph[v].size(); i++){
		const int u = graph[v][i].tar;
		if(graph[v][i].w < x){
			if(color[u] == color[v]){
				return false;
			}
			else if(!color[u] && !dfs(u, -col, x)){
				return false;
			}
		}
	}
	return true;
}

bool check(int64 x){
	memset(color, 0, sizeof(color));
	for(int i=0; i<N; i++)if(!color[i] && !dfs(i, 1, x)){
		return false;
	}
	return true;
}

int solve(){
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());

	if(check(compress.back() + 1)){
		return 0;
	}
	int low = 0, high = compress.size();
	for(;high-low>1;){
		int mid = (low + high) / 2;
		if(check(compress[mid])){
			low = mid;
		}
		else{
			high = mid;
		}
	}

	if(low == 0){
		return -1;
	}

	return (int)compress[low];
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}