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

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAX   211
using namespace std;
const int INF=INT_MAX;
int n;
vector<int> g[MAX];
int c[MAX][MAX];
int matx[MAX];
int maty[MAX];
int t[MAX];
int maxc,minc;
queue<int> q;
void minimize(int &x,const int &y) {
	if (x>y) x=y;
}
void maximize(int &x,const int &y) {
	if (x<y) x=y;
}
void init(void) {
	scanf("%d",&n);
	int i,j;
	maxc=-INF;
	minc=INF;
	for (i=1;i<=n;i=i+1)
		for (j=1;j<=n;j=j+1) {
			scanf("%d",&c[i][j]);
			maximize(maxc,c[i][j]);
			minimize(minc,c[i][j]);
		}
}
void loadgraph(const int &lim) {
	int i,j;
	for (i=1;i<=n;i=i+1) g[i].clear();
	for (i=1;i<=n;i=i+1)
		for (j=1;j<=n;j=j+1)
			if (c[i][j]<=lim) g[i].push_back(j);
}
int findway(const int &s) {
	while (!q.empty()) q.pop();
	int u,v,i;
	memset(t,0,sizeof t);
	q.push(s);
	while (!q.empty()) {
		u=q.front();q.pop();
		for (i=0;i<g[u].size();i=i+1) {
			v=g[u][i];
			if (t[v]==0 && v!=matx[u]) {
				t[v]=u;
				if (maty[v]==0) return (v);
				else q.push(maty[v]);
			}
		}
	}
	return (0);
}
void enlarge(int f) {
	int u,v;
	do {
		u=t[f];
		v=matx[u];
		matx[u]=f;
		maty[f]=u;
		f=v;
	}
	while (f!=0);
}
bool maxmatching(const int &lim) {
	loadgraph(lim);
	memset(matx,0,sizeof matx);
	memset(maty,0,sizeof maty);
	int i,t,r;
	for (i=1;i<=n;i=i+1) {
		t=findway(i);
		if (t!=0) enlarge(t);
	}
	r=0;
	for (i=1;i<=n;i=i+1) r+=(matx[i]!=0);
	return (r==n);
}
void process(void) {
	int l,m,r;
	l=minc;
	r=maxc;
	while (true) {
		if (l==r) {
			printf("%d",r);
			return;
		}
		if (r-l==1) {
			if (maxmatching(l)) printf("%d",l);
			else printf("%d",r);
			return;
		}
		m=(l+r)/2;
		if (maxmatching(m)) r=m;
		else l=m+1;
	}
}
int main(void) {
	//freopen("tmp.txt","r",stdin);	
	init();
	process();
	return 0;
}

Download