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

Download