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

970. Phân công hoàn thành sớm nhất

Mã bài: ASSIGN1

Có n người, n việc (1 < n ≤ 200). Người thứ i thực hiện công viêc j mất C[i,j] đơn vị thời gian. Giả sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi công việc cho mỗi người sao cho thời điểm hoàn thành công việc là sớm nhất có thể.

Input

- Dòng đầu: N
- Tiếp theo là ma trận C[i,j]. (thuộc kiểu Integer)

Output

- Ghi thời điểm sớm nhất hoàn thành.

Example

Input:
4
10 10 10 2
10 10 3 10
4 10 10 10
10 5 10 10
Output:
5

Link: http://vn.spoj.pl/problems/ASSIGN1/

Solution:

DevC:

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<set>

#define maxC 1000
#define maxN 1005
#define INF 10000005
#define DBG true


using namespace std;



int M,N,K;
int Fx[maxN],Fy[maxN];
int matchX[maxN],matchY[maxN];
int a[maxN][maxN];
int trace[maxN];
int start,finish;
int res=0;
int mid;

int getCost(int x,int y);
void findAugmentingPath();
void SubX_AddY();
void Solve();
void printMatch();


int main(){
    /*
    if(DBG){
            freopen("G_TEST.OUT","r",stdin);
            freopen("TEST.OUT","w",stdout);
    }
    */
    // read input
    scanf("%d",&M);
//    M=max(M,N);
    int x_,y_,c;
    
//    for(int i=1;i<=M;i++)
//    for(int j=1;j<=M;j++) a[i][j]=INF;
    
    for(int i=1;i<=M;i++)
    for(int j=1;j<=M;j++){
       scanf("%d",&c);     
       a[i][j]=c;
    }    
    Solve();
//    system("pause");
    return 0;    
}
int getCost(int x,int y){
    return a[x][y]-Fx[x]-Fy[y];
}
// find path begin vertex X-dinh start
void findAugmentingPath(){
     queue<int> Q;
     memset(trace,0,sizeof(trace));
     Q.push(start);
     while(!Q.empty()){
         int x=Q.front();
         Q.pop();
         // Xet nhung Y-dinh chua tham va la 0-canh
         for(int i=1;i<=M;i++)
             if(trace[i]==0 && a[x][i]<=mid){
                 trace[i]=x;
                 if(matchY[i]==0){ 
                     finish=i;
                     return;
                 }
                 Q.push(matchY[i]);
             }   
     }  
}
//
void SubX_AddY(){
     set<int> VisitedX;
     set<int> VisitedY;
     VisitedX.insert(start);
     for(int i=1;i<=M;i++){
         if(trace[i]!=0){
             VisitedX.insert(matchY[i]);
             VisitedY.insert(i);
         }
     }
     int delta=INF;
     for(int i=1;i<=M;i++)
         if(VisitedX.find(i)!= VisitedX.end())
             for(int j=1;j<=M;j++)
                if(VisitedY.find(j)==VisitedY.end()&& getCost(i,j)<delta){
                    delta=getCost(i,j);
                }
//     printf("delta=%d\n",delta);
     //  
     for(int i=1;i<=M;i++){
        if(VisitedX.find(i)!=VisitedX.end()) Fx[i]+=delta;
        if(VisitedY.find(i)!=VisitedY.end()) Fy[i]-=delta;
     }
}
// Mo rong cap ghep tai Y-dinh finish 
void Enlarge(){
     int next;
     int x;
     while(finish!=0){
         x=trace[finish];
         next=matchX[x];
         matchX[x]=finish;
         matchY[finish]=x;
         finish=next;
     }
}
//
void Solve(){
     int min_=1;
     int max_=(1<<31)-1;
     while(min_<max_){
         mid=((min_+max_)>>1);
         res=0;
         memset(matchX,0,sizeof(matchX));
         memset(matchY,0,sizeof(matchY));
         for(int i=1;i<=M;i++){
             start=i;
             finish=0;
             findAugmentingPath();
             if(finish==0) break;
             res++;
             Enlarge();
         }
         if(res==M) max_=mid;
         else min_=mid+1; 
     }
     printf("%d",min_);
}