ASSIGN1 - Phân công hoàn thành sớm nhất
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxn 444
using namespace std;
int n,c[maxn][maxn],a[maxn],b[maxn],d[maxn],q[maxn],mid,t;
int find()
{
int i,nq=0,x,y;
fr(i,1,n) d[i]=0;
fr(i,1,n)
if (!a[i])
{
nq++; q[nq]=i;
}
i=1;
while (i<=nq)
{
x=q[i++];
fr(y,1,n)
if (c[x][y]<=mid && !d[y])
{
d[y]=x;
if (!b[y])
{
t=y;
return 1;
}
nq++; q[nq]=b[y];
}
}
return 0;
}
void inc()
{
int x,y;
while (t)
{
x=d[t]; y=t;
t=a[x]; a[x]=y; b[y]=x;
}
}
int main()
{
int i,j,low=1000000,high=0,re,s;
cin >> n;
fr(i,1,n)
fr(j,1,n)
{
scanf("%d",&c[i][j]);
low=min(low,c[i][j]);
high=max(high,c[i][j]);
}
while (low<=high)
{
mid=(low+high)/2;
fr(i,1,n)
{
a[i]=0; b[i]=0;
}
while (find()) inc();
s=0;
fr(i,1,n)
if (a[i]) s++;
if (s==n)
{
high=mid-1; re=mid;
}
else low=mid+1;
}
cout << re << endl;
return 0;
}