ASSIGN1 - Phân công hoàn thành sớm nhất

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

#define mset(a,v) memset(a, v, sizeof a)
const int N = 200, INF = 1e9;
int g[N][N], n, my[N];
bool vy[N];

void enter() {
	cin >> n;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j) 
			cin >> g[i][j];
}

bool dfs(int s, int lim) {
	for(int u = 0; u < n; ++u) if(!vy[u] && g[s][u] <= lim) {
		vy[u] = true;
		if(my[u] == -1 || dfs(my[u], lim)) return my[u] = s, true;
	}
	return false;
}

int solve() {
	int l = 0, h = INF;
	while(l < h) {
		mset(my, -1); int mid = (l + h) / 2; bool ok = true;
		for(int i = 0; mset(vy, 0), i < n && ok; ++i) ok &= dfs(i, mid);
		if(ok) h = mid; else l = mid + 1;
	}
	return l;
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	cout << solve() << endl;
	return 0;
}

Download