【LibreOJ101】模板:最大流

LibreOJ https://loj.ac/p/101


#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
using namespace std;
#define add_edge(a,b,c) ++tot,nxt[tot]=head[a],head[a]=tot,to[tot]=b,cap[tot]=c
const int maxn = 105, maxm = 12450; //
int nxt[maxm], head[maxn], to[maxm];
long long cap[maxm]; // 注意必须开 long long,只要 s 多接几条 2^31-1 就会炸 int
int dis[maxn], q[maxn], cur[maxn];
int n, m, tot = 1, s, t;
// 是 ^ 而不是 ~ (也当然明显不能用'~')
bool BFS()
{
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    int st = 1, ed = 1, x;
    q[ed++] = s;
    while (st < ed)
    {
        x = q[st];
        ++st;
        for (int i = head[x]; i; i = nxt[i])
        {
            if (dis[to[i]] || (cap[i] == 0)) continue;
            dis[to[i]] = dis[x] + 1;
            q[ed++] = to[i];
        }
    }
    return (dis[t] != 0);
}
long long dfs(int x, long long maxflow) // long long
{
    if ( x == t || maxflow == 0 ) return maxflow;
    long long curflow = 0, flow;
    for ( int &i = cur[x]; i; i = nxt[i] ) // 多路增广
    {
        if ( cap[i] && ( dis[to[i]] == dis[x] + 1 ) )
        {
            if (flow = dfs(to[i], min(maxflow, cap[i])))
            {
                cap[i] -= flow; // 正向边减流量
                cap[i ^ 1] += flow; // 反向边加流量

                // cap 写成了 cur 
上一篇:P1401 城市


下一篇:ssm怎么导出数据库表为excel