HDU 4280 ISland Transport(最大流Dinic优化)

Description

T组样例，n点，m条双向边(独特，网络流多为单向边+反向边),输入n个点的坐标，找出从最左边的点到最右边的点的最大流

最大流模板题（卡超时）

用Dinic的话：

1. 数组开的够大，注意边的数目不同于点的数目
2. BFS里的queue改用数组模拟（STL耗时）
3. DFS采用“无cut[]”写法+flow == 0封锁优化
4. tem = DFS > 0时才加到答案里，等于0时不加
5. 多组输入cnt(边的计数器)一定要初始化，否则越攒越多TLE

Code(Dinic略优化)

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;
typedef long long ll;

int n, m, start, over;
int maxflow, deep[N];///deep深度

struct Edge
{
    int to, w, pre;
} a[N << 2];

//int cur[N];
int cnt = -1, head[N];

///cnt in this way can save the time
///我也试过cnt初始化为0，最后加个++cnt，但TLE
void add(int from, int to, int w)
{
    a[++cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
}

///数组模拟队列
bool bfs()///update deep[]
{
//    memset(deep, INF, sizeof(deep));
    memset(deep, -1, sizeof(deep));

    int q[N << 1];
    int fro, bac;
    fro = bac = 0;
    q[bac++] = start, deep[start] = 0;

    while(fro < bac)
    {
        int first = q[fro];
        if(first == over)
            return true;
        for(int i = head[first]; ~i; i = a[i].pre)
        {
            if(deep[ a[i].to ] == -1 && a[i].w > 0)
            {
                deep[ a[i].to ] = deep[first] + 1;
                q[bac++] = a[i].to;
            }
        }
        fro++;
    }
    return false;
}

///没有用cur[]数组......
int DFS(int s, int cap)
{
    if(s == over)
        return cap;

    int flow = 0, f;
    for(int i = head[s]; ~i; i = a[i].pre)
    {
        int to = a[i].to;
        if(deep[to] == deep[s] + 1 && a[i].w)
        {
            f = DFS(to, min(cap - flow, a[i].w));
            a[i].w -= f;
            a[i ^ 1].w += f;
            flow += f;
            if(flow == cap)
                break;
        }
    }
    ///TLE -> AC
    if(flow == 0)///某层DFS里某个flow为0
        deep[s] = -2;///封锁这个flow，避免无用的重复搜索
    return flow;
}

void Dinic()
{
    int tem = 0;
    while(bfs())
        while((tem = DFS(start, INF) )> 0)
            maxflow += tem;///不直接+DFS,可优化200ms
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        ///TLE -> AC
        maxflow = 0, cnt = -1;///多组输入cnt不初始化固然TLE
        memset(head, -1, sizeof(head));
        scanf("%d%d", &n, &m);
        start = over = 1;
        int x, y, z, x_min = INF, x_max = -INF;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &x, &y);
            if(x < x_min)
                start = i, x_min = x;
            if(x > x_max)
                over = i, x_max = x;
        }
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);///双向边的网络流(网络流通常单向边)
        }
        Dinic();
        cout << maxflow << '\n';
    }
    return 0;
}