LIGHT - Hệ thống đèn

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define INF 1000000000
typedef long long ll;
using namespace std;

int f[210][210],c[210][210];
int trace[210];
int n,m,k;
int cnt = 0;
int start,end;
vector<int> adj[210];

bool findPath()
{
//     cout << "begin findpath" << endl;
     memset(trace,0,sizeof(trace));
     queue<int> q;  q.push(start);  trace[start] = -1;
     while (!q.empty())
     {
           int u = q.front();  q.pop();
           for (int i = 0; i < adj[u].size(); i++)
           {
               int v = adj[u][i];
               if (!trace[v] && c[u][v] > f[u][v])
               {
                  trace[v] = u;
                  if (v == end) return true;
                  q.push(v);
               };
           };
     };
     return false;
};

void IncFlow()
{
     int delta = INF,v = end;
     while (v != start)
     {
           int u = trace[v];
           delta = min(delta,c[u][v] - f[u][v]);
           v = u;
     };
     v = end;
     while (v != start)
     {
           int u = trace[v];
           f[u][v] += delta;  f[v][u] -= delta;
           v = u;
     };
};

void add_edge(int u,int v,int cost)
{
     adj[u].push_back(v);
     adj[v].push_back(u);
     c[u][v] = cost;
};

void maxFlow()
{
     while (1)
     {
           if (!findPath()) break;
           IncFlow();           
     };
};

int main()
{
//    freopen("light.in","r",stdin);
//    freopen("light.ou","w",stdout);
    scanf("%d %d %d", &m, &n, &k);
    start = 1;  end = n + m + 2;
    memset(c,0,sizeof(c));
    for (int i = 1; i <= m; i++)
    {
        int x;  scanf("%d", &x);
        add_edge(start,1 + i,x);
    };
    for (int i = 1; i <= n; i++)
    {
        int x;  scanf("%d", &x);
        add_edge(m + i + 1,end,x);
    };
    for (int i = 0; i < k; i++)
    {
        int x,y;
        scanf("%d %d", &x, &y);
        add_edge(1 + x,m + 1 + y,INF);
    };
    
/*    for (int i = 1; i <= end; i++)
    {
        for (int j = 0; j < adj[i].size(); j++) cout << adj[i][j] << ' ';
        cout << endl;        
    };*/
    
    memset(f,0,sizeof(f));
    maxFlow();
    int ret = 0;
    for (int i = 0; i < adj[start].size(); i++)
    {
        int v = adj[start][i];
        ret += f[start][v];
    };
    printf("%d\n", ret);
};

Download