网络流最大流dinic

hdu 6214

#include <bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define TS printf("!!!\n")

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = ; //点数的最大值

const int MAXM = ; //边数的最大值

struct Node

{

        int from, to, next;

        int cap;

} edge[MAXM];

int tol;

int dep[MAXN];//dep为点的层次

int head[MAXN];

int n;

void init()

{

        tol = ;

        memset(head, -, sizeof(head));

}

void addedge(int u, int v, int w) //第一条变下标必须为偶数

{

        edge[tol].from = u;

        edge[tol].to = v;

        edge[tol].cap = w;

        edge[tol].next = head[u];

        head[u] = tol++;

        edge[tol].from = v;

        edge[tol].to = u;

        edge[tol].cap = ;

        edge[tol].next = head[v];

        head[v] = tol++;

}

int BFS(int start, int end)

{

        int que[MAXN];

        int front, rear;

        front = rear = ;

        memset(dep, -, sizeof(dep));

        que[rear++] = start;

        dep[start] = ;

        while (front != rear)

        {

                int u = que[front++];

                if (front == MAXN)

                {

                        front = ;

                }

                for (int i = head[u]; i != -; i = edge[i].next)

                {

                        int v = edge[i].to;

                        if (edge[i].cap >  && dep[v] == -)

                        {

                                dep[v] = dep[u] + ;

                                que[rear++] = v;

                                if (rear >= MAXN)

                                {

                                        rear = ;

                                }

                                if (v == end)

                                {

                                        return ;

                                }

                        }

                }

        }

        return ;

}

int dinic(int start, int end)

{

        int res = ;

        int top;

        int stack[MAXN];//stack为栈，存储当前增广路

        int cur[MAXN];//存储当前点的后继

        while (BFS(start, end))

        {

                memcpy(cur, head, sizeof(head));

                int u = start;

                top = ;

                while ()

                {

                        if (u == end)

                        {

                                int min = INF;

                                int loc;

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

                                        if (min > edge[stack[i]].cap)

                                        {

                                                min = edge[stack[i]].cap;

                                                loc = i;

                                        }

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

                                {

                                        edge[stack[i]].cap -= min;

                                        edge[stack[i] ^ ].cap += min;

                                }

                                res += min;

                                top = loc;

                                u = edge[stack[top]].from;

                        }

                        for (int i = cur[u]; i != -; cur[u] = i = edge[i].next)

                                if (edge[i].cap !=  && dep[u] +  == dep[edge[i].to])

                                {

                                        break;

                                }

                        if (cur[u] != -)

                        {

                                stack[top++] = cur[u];

                                u = edge[cur[u]].to;

                        }

                        else

                        {

                                if (top == )

                                {

                                        break;

                                }

                                dep[u] = -;

                                u = edge[stack[--top]].from;

                        }

                }

        }

        return res;

}

int main()

{

        int time;

        cin >> time;

        int st, tp;

        int u, v, w;

        while (time--)

        {

                init();

                int n, m;

                scanf("%d %d", &n, &m);

                scanf("%d %d", &st, &tp);

                //TS;

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

                {

                        scanf("%d %d %d", &u, &v, &w);

                        addedge(u, v, w *  + );

                }

                //TS;

                cout << dinic(st,tp) %  << endl;

        }

}