LIGHT - Hệ thống đèn

Tác giả: hieult

Ngôn ngữ: C++

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <conio.h>
#define maxc 1111111111
#define maxn 311

using namespace std;

int n,m,k,s,t,c[maxn][maxn],f[maxn][maxn],qu[maxn],tr[maxn];

bool coduongtang(){
     int dau,cuoi,u,v;
     memset(tr,0,sizeof(tr));
     dau = 1; cuoi = 1;
     qu[dau] = s;
     tr[s] = n+m+3;
    // printf("co\n");
     do{
           u = qu[dau]; dau++;
           for(v = 1;v<=n+m+2;v++){
                if(tr[v]==0 && c[u][v]>f[u][v]){
                     tr[v] = u;
                     if(v==t)
                          return true;
                     cuoi++; qu[cuoi] = v;
                }
           }
     }while(dau<=cuoi);
     return false;
}

void duongtang(){
     int delta,u,v;
     delta = maxc;
     v = t;
     do{
         u = tr[v];
         if(c[u][v]-f[u][v]<delta) delta = c[u][v]-f[u][v];
         v = u;
     }while(v!=s);
     v = t;
     do{
         u = tr[v];
         f[u][v] = f[u][v]+delta;
         f[v][u] = f[v][u]-delta;
         v = u;
     }while(v!=s);
}

int main(){
     //freopen("LIGHT.in","r",stdin);
     int i,u,v;
     scanf("%d %d %d",&m,&n,&k);
     memset(c,0,sizeof(c));
     for(int i = 1;i<=m;i++) scanf("%d",&c[1][i+1]);
     for(int i = 1;i<=n;i++) scanf("%d",&c[m+i+1][n+m+2]);
     for(int i = 1;i<=k;i++){
          scanf("%d %d",&u,&v);
          c[u+1][m+v+1] = maxc;
     }
     s = 1;
     t = n+m+2;
     memset(f,0,sizeof(f));
     do{
          if(coduongtang()) duongtang();
          else break;
     }while(true);
     int w = 0;
     for(u = 1;u<=n+m+2;u++){
          if(f[s][u]>0)
              w+=f[s][u];
     }
     printf("%d",w);
     //getch();
}

Download