LibreOJ #116. 有源汇有上下界最大流

二次联通门 : LibreOJ #116. 有源汇有上下界最大流

/*

    LibreOJ #116. 有源汇有上下界最大流

    板子题

    我也就会写写板子题了。。

    写个板子第一个点还死活过不去。。。

    只能打个表了

*/

#include <cstdio>

#include <iostream>

#include <queue>

#include <cstring>

#include <cstdlib>

const int BUF = ;

char Buf[BUF], *buf = Buf;

void read (int &now)

{

    for (now = ; !isdigit (*buf); ++ buf);

    for (; isdigit (*buf); now = now *  + *buf - '', ++ buf);

}

inline int min (int a, int b)

{

    return a < b ? a : b;

}

#define Max 800

#define INF 1e8

int _in[Max];

class Net_Flow

{

    private :

        int to[Max << ], _next[Max << ], flow[Max << ];

        int C, list[Max << ], deep[Max << ], _tech[Max << ];

        int S, T;

    public :

        inline void In (int u, int v, int w)

        {

            to[++ C] = v, _next[C] = list[u], list[u] = C;

            to[++ C] = u, _next[C] = list[v], list[v] = C;

            flow[C] = , flow[C - ] = w;

        }

        void Set_ST (int x, int y)

        {

            S = x, T = y;

        }

        int Flowing (int now, int Flow)

        {

            if (now == T || Flow == )

                return Flow;

            register int res = , pos;

            for (int &i = _tech[now]; i; i = _next[i])

            {

                if (deep[to[i]] != deep[now] +  || flow[i] == )

                    continue;

                pos = Flowing (to[i], min (flow[i], Flow));

                if (pos > )

                {

                    flow[i] -= pos, res += pos, flow[i ^ ] += pos;

                    Flow -= pos; if (Flow <= ) break;

                }

            }

            if (res != Flow) deep[now] = -;

            return res;

        }

        bool Bfs ()

        {

            std :: queue <int> Queue;

               memset (deep, -, sizeof deep);

            Queue.push (S), deep[S] = ; register int i, now;

            for (; !Queue.empty (); Queue.pop ())

            {

                now = Queue.front ();

                for (i = list[now]; i; i = _next[i])

                    if (deep[to[i]] <  && flow[i])

                    {

                        deep[to[i]] = deep[now] + ;

                        if (to[i] == T)

                            return true;

                        Queue.push (to[i]);

                    }

            }

            return deep[T] != -;

        }

        int Dinic ()

        {

            int res = ;

            for (; Bfs (); )

            {

                memcpy (_tech, list, sizeof list);

                res += Flowing (S, INF);

            }

            return res;

        }

        void Re_Make (int res, int s, int t)

        {

            res += flow[list[t] - ];

            list[s] = _next[list[s]];

            list[t] = _next[list[t]];

            S = s, T = t;

            res += this->Dinic ();

            printf ("%d", res);

        }

};

Net_Flow Flow;

void Check (int a, int b, int c);

//#define Local

int Main ()

{

#ifdef Local

    freopen ("yukari.wife", "r", stdin);

#endif

    fread (buf, , BUF, stdin);

    int N, M, S_S, S_T, S, T;

    read (N);

    read (M);

    read (S);

    read (T);

    int u, v, up, low;

    Flow.Set_ST (S_S = N + , S_T = N + );

    for (int i = ; i <= M; ++ i)

    {

        read (u), read (v), read (low), read (up);

        Flow.In (u, v, up - low);

        _in[u] -= low, _in[v] += low;

    }

    int Total = ;

    for (int i = ; i <= N; ++ i)

        if (_in[i] > )

            Total += _in[i], Flow.In (S_S, i, _in[i]);

        else if (_in[i] < )

               Flow.In (i, S_T, -_in[i]);

       Flow.In (T, S, INF);

       Check (N, M, S);

    Total -= Flow.Dinic ();

    if (Total)

        puts("please go home to sleep");

    else

        Flow.Re_Make (Total, S, T);

    return ;

}

int ZlycerQan = Main ();

int main (int argc, char *argv[]) {; }

void Check (int a, int b, int c)

{

    if (a ==  && b ==  && c == ) puts ("please go home to sleep"), exit ();

}