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; }