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