这里是网络流的主页

1. 最大流

    const int INF = 0x3f3f3f3f;
    const int MAXN = 5e2 + 5, MAXM = 5e5 + 5;
   
    struct Edge
    {
        int v, f, next;
    };
   
    int src, sink;
    int head[MAXN];
    int nume;
    Edge e[MAXM];
   
    void addEdge(int u, int v, int c)//链表的头插入
    {
        e[++nume].v = v;
        e[nume].f = c;
        e[nume].next = head[u];
        head[u] = nume;
        e[++nume].v = u;
        e[nume].f = 0;
        e[nume].next = head[v];
        head[v] = nume;
    }
   
    void init()
    {
        memset(head, 0, sizeof(head));
        nume = 1;
    }
   
    queue<int> q;
    bool vis[MAXN];
    int dist[MAXN];//depth
   
    void bfs()
    {
        memset(dist, 0, sizeof(dist));
        while(!q.empty()) q.pop();
        vis[src] = true;
        q.push(src);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = head[u]; i; i = e[i].next)
            {
                if(e[i].f && ! vis[e[i].v])
                {
                    q.push(e[i].v);
                    dist[e[i].v] = dist[u] + 1;
                    vis[e[i].v] = true;
                }
            }
        }
    }
   
    int dfs(int u, int delta)
    {
        if(u == sink) return delta;
        else
        {
            int rest = 0;
            for(int i = head[u]; delta && i; i = e[i].next)
            {
                if(e[i].f && dist[e[i].v] == dist[u] + 1)
                {
                    int dd = dfs(e[i].v, min(e[i].f, delta));
                    e[i].f -= dd;
                    e[i ^ 1].f += dd;
                    delta -= dd;
                    rest += dd;
                }
            }
            return rest;
        }
    }
   
    int maxFlow()
    {
        int rest = 0;
        while(true)
        {
            memset(vis, 0, sizeof(vis));
            bfs();
            if(!vis[sink]) return rest;
            rest += dfs(src, INF);
        }
    }
   

2. 费用流

    const int MAXNODE = 605;
    const int INF = 0x3f3f3f3f;
   
    struct Edge
    {
        int to, f, c, next;// to flow cost next
        Edge(int _to, int _f, int _c, int _next): to(_to), f(_f), c(_c), next(_next) {}
        Edge() {}
    };
   
    Edge edge[MAXNODE * MAXNODE];
    int head[MAXNODE], total = 1;
    bool vis[MAXNODE];
   
    void addEdge(int u, int v, int f, int c)
    {
        edge[++total] = Edge(v, f, c, head[u]);
        head[u] = total;
        edge[++total] = Edge(u, 0, -c, head[v]);
        head[v] = total;
    }
   
    queue<int> q;
    int dis[MAXNODE], pren[MAXNODE], pree[MAXNODE];
   
    bool findPath(int start, int end)
    {
        while(!q.empty()) q.pop();
        q.push(start);
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[start] = 0;
        vis[start] = true;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = head[u]; i != -1; i = edge[i].next)
            {
                int v = edge[i].to;
                if(edge[i].f > 0 && dis[u] + edge[i].c < dis[v])
                {
                    dis[v] = dis[u] + edge[i].c;
                    pren[v] = u;
                    pree[v] = i;
                    if(!vis[v])
                    {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
            vis[u] = false;
        }
        return dis[end] < INF;
    }
   
    int augment(int start, int end)
    {
        int u = end;
        int delta = INF;
        int ans = 0;
        while(u != start)
        {
            delta = min(delta, edge[pree[u]].f);
            u = pren[u];
        }
        u = end;
        while(u != start)
        {
            edge[pree[u]].f -= delta;
            edge[pree[u] ^ 1].f += delta;
            u = pren[u];
            ans += edge[pree[u]].c * delta;
        }
        //printf("ans %d\n", ans);
        //printf("dis %d * delta %d = %d\n", dis[end], delta, dis[end] * delta);
        return ans;
    }
   
    int minCostFlow(int start, int end)
    {
        /*这个函数感觉哪里不对。。。。*/
        int cur = 0;
        while(findPath(start, end))
        {
            cur += augment(start, end);
            //if(cur < ans) ans = cur;
        }
        return cur;
    }
   
    void init()
    {
        memset(head, -1, sizeof(head));
        total = 1;
    }