网络流【最大流、上下界可行流、最小割、最小割树、费用流】Summary

知识点总结

Dinic最大流 网络流

Attention

要注意链式前向星的init()时$e = 1$因为取一条边的反向边的时候要^1

Problems

hdu5988 Coding Contest

Description

给出n个点和m条边，每个点有si个人，bi份食物,每条边一开始可以通过一个人,后来的人每通过一个就有pi的概率使整个系统崩溃,问崩溃的最小的概率是多少

Solution

求最小崩溃的概率可以转化成求最大不崩溃的概率，然后跑最小费用最大流 把每个点的人数看成需要流出的流量，食物看成需要流入的流量 然后对概率取个log，把乘法变成加法，最后再乘回去即可。 要注意SPFA中判断要加eps，否则精度会炸

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1000 + 10, Maxm = 200000 + 10, inf = INT_MAX;
const double eps = 1e-14;

int N, M;
int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm];
int Cur[Maxm];
double Cost[Maxm];
int S, T;

inline void Init()
{
    e = 0;
    memset(Begin, -1, sizeof(Begin));
}

inline void add_edge (int x, int y, int z, double l)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e] = z;
    Cost[e++] = l;
    swap(x, y);
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e] = 0;
    Cost[e++] = -l;
}

double Dis[Maxn];
int Vis[Maxn], level[Maxn];

inline int SPFA()
{
    for (int i = 0; i <= N + 1; ++i) Dis[i] = inf * 1.0, Vis[i] = 0;
    queue <int> Q;
    Q.push(S);
    Dis[S] = 0.0;
    Vis[S] = 1;
    while (!Q.empty())
    {
        int x = Q.front(); Q.pop();
        //cout<<"*"<<x<<endl;
        Vis[x] = 0;
        for (int i = Begin[x]; i + 1; i = Next[i])
        {
            int y = To[i];
            //cout<<"$"<<y<<endl;
            //cout<<W[i]<<" "<<Dis[y]<<" "<<Dis[x]<<" "<<Cost[i]<<endl;
            if (W[i] > 0 && Dis[y] > Dis[x] + Cost[i] + eps)
            {
                //cout<<"$"<<y<<endl;
            //  cout<<Dis[y]<<" "<<Dis[x]<<" "<<Cost[i]<<endl;
                Dis[y] = Dis[x] + Cost[i];
            //  cout<<Dis[y]<<endl;
                if (!Vis[y]) {Vis[y] = 1;Q.push(y);}
            }
        }
    //  cout<<endl;
    }
    if (Dis[T] == inf) return 0;
    return 1;
}

inline int find (int x, int k)
{
    Vis[x] = 1;
    //cout<<x<<" "<<k<<endl;
    if (x == T) return k;
    for (int &i = Cur[x]; i + 1; i = Next[i])
    {
        int y = To[i], sum;
//      cout<<Dis[y]<<" "<<Dis[x] + Cost[i]<<endl;
        if (!Vis[y] && W[i] > 0 && Dis[y] == Dis[x] + Cost[i] && (sum = find(y, min(k, W[i]))))
        {
            W[i] -= sum;
            W[i ^ 1] += sum;
            return sum;
        }
    }
    return 0;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int t;
    scanf("%d", &t);

    while (t--)
    {
        scanf("%d%d", &N, &M);
        S = 0, T = N + 1;
        Init();
        for (int i = 1; i <= N; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            add_edge(S, i, x, 0.0);
            add_edge(i, T, y, 0.0);
            //cout<<S<<" "<<i<<" "<<T<<endl;
        }

        for (int i = 1; i <= M; ++i)
        {
            int x, y, z;
            double l;
            scanf("%d%d%d%lf", &x, &y, &z, &l);
            l = -log(1 - l);
            add_edge(x, y, z - 1, l);
            add_edge(x, y, 1, 0.0);
        }

        double Ans = 0;
        while (SPFA())
        {
            //cout<<"#"<<Dis[T]<<endl;
            //cout<<"Begin"<<endl;
            for (int i = 0; i <= N + 1; ++i) Cur[i] = Begin[i];
            memset(Vis, 0, sizeof(Vis));
            Ans += find(S, inf) * Dis[T];
            //cout<<"End"<<endl;
        }
        printf("%.2lf\n", 1 - exp(-Ans));
    }
    return 0;
}

hdu3549 Flow Problem

Description

最大流模板

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 20, Maxm = 1000 + 10, inf = INT_MAX;

int N, M;
int e, Begin[Maxn], Next[Maxm * 2], To[Maxm * 2], W[Maxm * 2], Cur[Maxn];
int level[Maxn], Vis[Maxn];

inline void Init()
{
    e = 0;
    memset(Begin, -1, sizeof (Begin));
    memset(W, 0, sizeof (W));
}

inline void add_edge (int x, int y, int z)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e++] = z;
}

queue <int> Q;

inline int bfs ()
{
    for (int i = 1; i <= N; ++i)
        level[i] = -1, Vis[i] = 0;
    level[1] = 0;
    while (!Q.empty()) Q.pop();
    Q.push(1);
    while (!Q.empty())
    {
        int x = Q.front(); Q.pop();
        if (Vis[x]) continue;
        Vis[x] = 1;
        for (int i = Begin[x]; i + 1; i = Next[i])
        {
            int y = To[i];
            if (W[i] > 0 && level[y] < 0)
            {
                level[y] = level[x] + 1;
                Q.push(y);
            }
        }
    }
    if (level[N] < 0) return 0;
    return 1;
}

inline int find (int x, int k)
{
    if (x == N) return k;
    for (int &i = Cur[x]; i + 1; i = Next[i])
    {
        int y = To[i], sum;
        if (W[i] > 0 && level[y] == level[x] + 1 && (sum = find (y, min(k, W[i]))))
        {
            W[i] -= sum;
            W[i ^ 1] += sum;
            return sum;
        }
    }
    return 0;
}

int main()
{
#ifdef hk_cnyali
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
#endif
    int T, Cnt = 0;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d%d", &N, &M);
        Init();
        while (M--)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add_edge(x, y, z);
            add_edge(y, x, 0);
        }
        for (int i = 1; i <= N; ++i) Cur[i] = Begin[i];

        int Ans = 0;
        while (bfs())
        {
            int Sum = 0;
            for (int i = 1; i <= N; ++i) Cur[i] = Begin[i];
            while (Sum = (find(1, inf)))
                Ans += Sum;
        }
        printf("Case %d: %d\n", ++Cnt, Ans);
    }
    return 0;
}

hdu3657 Game

Description

给你一个n×m的矩阵，矩阵的值表示选择这个格子所能获得的得分，如果相邻的格子被选择（四联通）的话，就要减掉一个2 * (两个格子值'与'的结果)。题目会钦定K个点必须选。求最大能获得的得分

Solution

这道题建图的方法比较巧妙。我们可以先假设全部的格子都选了，然后从中间去掉一些点使得去掉这些点的代价最小。于是就转化成了最小割问题。我们根据坐标奇偶性建图，跑一遍最小割即可。（具体建图方法见代码）

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 3000, Maxm = 200000 + 10, inf = INT_MAX;

int N, M, K;
int p[Maxn], A[Maxn];
int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm], Cur[Maxm];
int S, T;

inline void Init()
{
    S = 0, T = N * M + 1;
    e = 0;
    memset(Begin, -1, sizeof Begin);
}

inline void add_edge (int x, int y, int z)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e++] = z;
    swap(x, y);
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e++] = 0;
}

int dr[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int level[Maxn];

inline int bfs ()
{
    queue <int> Q;
    for (int i = S; i <= T; ++i) level[i] = -1;
    level[S] = 0;
    Q.push(S);
    while (!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for (int i = Begin[x]; i + 1; i = Next[i])
        {
            int y = To[i];
            //cout << "*" << y << endl;
            if (W[i] > 0 && level[y] < 0)
            {
                level[y] = level[x] + 1;
                Q.push(y);
            }
        }
    }
//  cout<<level[T]<<endl;
    return level[T] != -1;
}

inline int find (int x, int k)
{
    if (x == T) return k;
    for (int &i = Cur[x]; i + 1; i = Next[i])
    {
        int y = To[i], sum;
        if (W[i] > 0 && level[y] == level[x] + 1 && (sum = find(y, min(k, W[i]))))
        {
            W[i] -= sum;
            W[i ^ 1] += sum;
            return sum;
        }
    }
    return 0;
}

int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    while (scanf("%d%d%d", &N, &M, &K) != EOF)
    {
        Init();
        int Sum = 0;
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
            {
                int x;
                scanf("%d", &x);
                Sum += x;
                p[M * (i - 1) + j] = x;
                A[M * (i - 1) + j] = x;
            }

        while (K--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            p[M * (x - 1) + y] = inf;
        }

        for (int i = 1; i <= N; ++i)
        {
            for (int j = 1; j <= M; ++j)
            {
                int id = M * (i - 1) + j;
                if (!((i + j) & 1))
                {
                    add_edge (S, id, p[id]);
                    for (int k = 0; k < 4; ++k)
                    {
                        int x = i + dr[k][1], y = j + dr[k][0];
                        if (x < 1 || x > N || y < 1 || y > M) continue;
                        int id2 = M * (x - 1) + y;
                        add_edge (id, id2, 2 * (A[id] & A[id2]));
                    }
                }
                else
                    add_edge (id, T, p[id]);
            }
        }
    //  cout<<e<<endl;

        while (bfs())
        {
    //      cout<<"fuck"<<endl;
            for (int i = S; i <= T; ++i)
                Cur[i] = Begin[i];
            int sum = 0;
            while (sum = find(S, inf))
                Sum -= sum;
        }

        cout<<Sum<<endl;
    }
    return 0;
}

hdu3987 Harry Potter and the Forbidden Forest

Description

求最小割中边数最小的一组割

Solution

先跑一边最大流，然后把满流的边（即可能成为答案的边）设为1，其他的边设为inf，再跑一边最大流即为答案

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1000 + 10, Maxm = 200000 + 10, inf = INT_MAX;

int N, M, e, Begin[Maxn], To[Maxm * 2], Next[Maxm * 2], W[Maxm * 2];
int X[Maxm * 2], Y[Maxm * 2], Z[Maxm * 2];
int Cur[Maxm * 2], level[Maxn];

inline void Init()
{
    e = 0;
    memset(Begin, -1, sizeof(Begin));
}

inline void add_edge (int x, int y, int z)
{
    X[e] = x, Y[e] = y, Z[e] = z;
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e++] = z;
}

queue <int> Q;
inline int bfs ()
{
    while (!Q.empty()) Q.pop();
    for (int i = 1; i <= N; ++i) level[i] = -1;
    Q.push(1);
    level[1] = 0;

    while (!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for (int i = Begin[x]; i + 1; i = Next[i])
        {
            int y = To[i];
            if (W[i] > 0 && level[y] < 0)
            {
                level[y] = level[x] + 1;
                Q.push(y);
            }
        }
    }
    if (level[N] < 0) return 0;
    return 1;
}

inline int find (int x, int k)
{
    if (x == N) return k;
    for (int &i = Cur[x]; i + 1; i = Next[i])
    {
        int y = To[i], sum;
        if (W[i] > 0 && level[y] == level[x] + 1 && (sum = find(y, min(k, W[i]))))
        {
            //cout<<sum<<endl;
            W[i] -= sum;
            W[i ^ 1] += sum;
            return sum;
        }
    }
    return 0;
}

int main()
{
#ifdef hk_cnyali
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif

    int T;
    scanf("%d", &T);
    int cntt = 0;
    while (T--)
    {
        scanf("%d%d", &N, &M);
        Init();
        for (int i = 1; i <= M; ++i)
        {
            int x, y, z, z1;
            scanf("%d%d%d%d", &x, &y, &z, &z1);
            x++, y++;
            add_edge(x, y, z);
            add_edge(y, x, 0);
            if (z1) add_edge(y, x, z), add_edge(x, y, 0);
        }

        while (bfs())
        {
            for (int i = 1; i <= N; ++i) Cur[i] = Begin[i];
//          for  (int i = 0; i <= e; ++i) cout<<W[i]<<" ";
//          cout<<endl;
            while (find(1, inf));
        }

        for (int i = 0; i < e; i += 2)
        {
            if (!W[i]) W[i] = 1, W[i ^ 1] = 0;
            else W[i] = inf, W[i ^ 1] = 0;
        }

        int Ans = 0, sum;
        while (bfs())
        {
            for (int i = 1; i <= N; ++i) Cur[i] = Begin[i];
            while (sum = find(1, inf))
                Ans += sum;
        }

        printf("Case %d: %d\n", ++cntt, Ans);
    }
    return 0;
}

hdu4940 Destroy Transportation system

Description

无源无汇上下界可行流模板

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 200 + 10, Maxm = 10000 + 10, inf = INT_MAX;

int e, Begin[Maxn], To[Maxm * 2], Next[Maxm * 2], W[Maxm * 2];
int Cur[Maxn];
int In[Maxn], S, T;
int upper[Maxm], lowwer[Maxm];
int level[Maxn];

int N, M;

inline void Init()
{
    e = 0;
    memset (Begin, -1, sizeof Begin);
    memset (In, 0, sizeof In);
    S = 0, T = N + 1;
}

inline void add_edge (int x, int y, int z)
{
    To[e] = y; Next[e] = Begin[x];
    Begin[x] = e; W[e++] = z;
    swap(x, y);
    To[e] = y; Next[e] = Begin[x];
    Begin[x] = e; W[e++] = 0;
}

inline int bfs ()
{
    queue <int> Q;
    for (int i = S; i <= T; ++i) level[i] = -1;
    level[S] = 0;
    Q.push(S);
    while (!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for (int i = Begin[x]; i + 1; i = Next[i])
        {
            int y = To[i];
            if (W[i] > 0 && level[y] < 0)
            {
                level[y] = level[x] + 1;
                Q.push(y);
            }
        }
    }
    return level[T] != -1;
}

inline int find (int x, int k)
{
    if (x == T) return k;
    for (int &i = Cur[x]; i + 1; i = Next[i])
    {
        int y = To[i], sum;
        if (W[i] > 0 && level[y] == level[x] + 1 && (sum = find(y, min(k, W[i]))))
        {
            W[i] -= sum;
            W[i ^ 1] += sum;
            return sum;
        }
    }
    return 0;
}

int main()
{
#ifdef hk_cnyali
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    for (int xz = 1; xz <= t; ++xz)
    {
        scanf("%d%d", &N, &M);
        Init();
        for (int i = 1; i <= M; ++i)
        {
            int x, y, u, l;
            scanf("%d%d%d%d", &x, &y, &u, &l);
            add_edge (x, y, l);
    //      cout<<x<<" "<<y<<" "<<l<<endl;
            In[y] += u;
            In[x] -= u;
        }

        int cnt = 0;
        for (int i = 1; i <= N; ++i)
        {
        //  cout<<In[i]<<endl;
            if (In[i] > 0) add_edge (S, i, In[i]), cnt += In[i];
            else add_edge (i, T, -In[i]);
        }

        int Ans = 0;
        while (bfs())
        {
            for (int i = S; i <= T; ++i) Cur[i] = Begin[i];
            int sum;
            while (sum = find(S, inf))Ans += sum;
        }

        printf("Case #%d: ", xz);
        if (cnt == Ans)
            cout<<"happy"<<endl;
        else cout<<"unhappy"<<endl;
    }
    return 0;
}

hdu4862 Jump

Description

给定一个n*m的矩形(n,m≤10),每个矩形中有一个0~9的数字。 　　一共可以进行k次游戏，每次游戏可以任意选取一个没有经过的格子为起点，并且跳任意多步，每步可以向右方和下方跳。每次跳需要消耗两点间的曼哈顿距离减一的能量，若每次跳的起点和终点的数字相同，可以获得该数字的能量。（能量可以为负） 　　询问k次或更少次游戏后是否可以经过所有的格子，若可以求出最大的剩余能量。

Solution

建图的时候把每个点拆成两部分， 从S向左半部分连cap为1，cost为0的边，从右边部分向T连cap为1，cost为0的边 然后向每个可以到达的点连一条cap为1，cost为题目中所说的值的边，不过要建负的，最后再取相反数（因为是要使能量最大） 然后还要再新建一个点，由S向这个点连一条cap为K，cost为0的边，这样保证在K步之内有解 然后跑一遍最大流，如果最大流==N×M，则输出最小费用。否则输出-1

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 200 + 10, Maxm = 10000 + 10, inf = INT_MAX;

int e, Begin[Maxn], To[Maxm * 2], Next[Maxm * 2], W[Maxm * 2];
int Cur[Maxn];
int In[Maxn], S, T;
int upper[Maxm], lowwer[Maxm];
int level[Maxn];

int N, M;

inline void Init()
{
    e = 0;
    memset (Begin, -1, sizeof Begin);
    memset (In, 0, sizeof In);
    S = 0, T = N + 1;
}

inline void add_edge (int x, int y, int z)
{
    To[e] = y; Next[e] = Begin[x];
    Begin[x] = e; W[e++] = z;
    swap(x, y);
    To[e] = y; Next[e] = Begin[x];
    Begin[x] = e; W[e++] = 0;
}

inline int bfs ()
{
    queue <int> Q;
    for (int i = S; i <= T; ++i) level[i] = -1;
    level[S] = 0;
    Q.push(S);
    while (!Q.empty())
    {
        int x = Q.front(); Q.pop();
        for (int i = Begin[x]; i + 1; i = Next[i])
        {
            int y = To[i];
            if (W[i] > 0 && level[y] < 0)
            {
                level[y] = level[x] + 1;
                Q.push(y);
            }
        }
    }
    return level[T] != -1;
}

inline int find (int x, int k)
{
    if (x == T) return k;
    for (int &i = Cur[x]; i + 1; i = Next[i])
    {
        int y = To[i], sum;
        if (W[i] > 0 && level[y] == level[x] + 1 && (sum = find(y, min(k, W[i]))))
        {
            W[i] -= sum;
            W[i ^ 1] += sum;
            return sum;
        }
    }
    return 0;
}

int main()
{
#ifdef hk_cnyali
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    for (int xz = 1; xz <= t; ++xz)
    {
        scanf("%d%d", &N, &M);
        Init();
        for (int i = 1; i <= M; ++i)
        {
            int x, y, u, l;
            scanf("%d%d%d%d", &x, &y, &u, &l);
            add_edge (x, y, l);
    //      cout<<x<<" "<<y<<" "<<l<<endl;
            In[y] += u;
            In[x] -= u;
        }

        int cnt = 0;
        for (int i = 1; i <= N; ++i)
        {
        //  cout<<In[i]<<endl;
            if (In[i] > 0) add_edge (S, i, In[i]), cnt += In[i];
            else add_edge (i, T, -In[i]);
        }

        int Ans = 0;
        while (bfs())
        {
            for (int i = S; i <= T; ++i) Cur[i] = Begin[i];
            int sum;
            while (sum = find(S, inf))Ans += sum;
        }

        printf("Case #%d: ", xz);
        if (cnt == Ans)
            cout<<"happy"<<endl;
        else cout<<"unhappy"<<endl;
    }
    return 0;
}