QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#756209#143. 最大流(随机数据)Vegetable_DogCompile Error//C++233.0kb2024-11-16 19:21:592024-11-16 19:21:59

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 19:21:59]
  • 评测
  • [2024-11-16 19:21:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define Rep(i, a, b) for (int i = a; i >= (b); i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define SZ(x) (int)(x.size())
#define lowbit(x) ((x) & -(x))
using db = double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using i128 = __int128_t;
// Think twice, code once

struct Dinic {
const int N = 205;
const int inf = LONG_LONG_MAX;
struct Edge {
    int from, to, cap, flow;
};

bool operator<(const Edge &a, const Edge &b) {
    return a.from < b.from || (a.from == b.from && a.to < b.to);
}

int n, m, s, t;
vector<Edge> edges;  // 边数的两倍
vector<int> G[N];    // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[N];         // BFS使用
int d[N];            // 从起点到i的距离
int cur[N];          // 当前弧指针

void init(int _n) {
    n = _n;
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
}

void add(int from, int to, int cap) {
    edges.push_back((Edge){from, to, cap, 0});
    edges.push_back((Edge){to, from, 0, 0});
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
}

bool BFS() {  //  最后一次bfs走过的都是交错路径,可用于二分图博弈判断H点是否必须
    memset(vis, 0, sizeof(int) * n);
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    d[s] = 0;
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (int i = 0; i < G[x].size(); i++) {
            Edge &e = edges[G[x][i]];
            if (!vis[e.to] && e.cap > e.flow) {
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}

int DFS(int x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f;
    for (int &i = cur[x]; i < G[x].size(); i++) {
        Edge &e = edges[G[x][i]];
        if (d[x] + 1 == d[e.to] &&
            (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
            e.flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
            if (a == 0) break;
        }
    }
    return flow;
}

int Maxflow(int _s, int _t) {
    s = _s, t = _t;
    int flow = 0;
    while (BFS()) {
        memset(cur, 0, sizeof(int) * n);
        flow += DFS(s, inf);
    }
    return flow;
}
} g;
void solve() {
    int n, m, s, t; cin >> n >> m >> s >> t; s--, t--;
    g.init(n);
    while (m--) {
        int u, v, c; cin >> u >> v >> c; u--, v--;
        g.add(u, v, c);
    }
    cout << g.Maxflow(s, t) << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

Details

answer.code:28:6: error: ‘bool Dinic::operator<(const Edge&, const Edge&)’ must have exactly one argument
   28 | bool operator<(const Edge &a, const Edge &b) {
      |      ^~~~~~~~
answer.code:34:15: error: invalid use of non-static data member ‘Dinic::N’
   34 | vector<int> G[N];    // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
      |               ^
answer.code:22:11: note: declared here
   22 | const int N = 205;
      |           ^
answer.code:35:10: error: invalid use of non-static data member ‘Dinic::N’
   35 | bool vis[N];         // BFS使用
      |          ^
answer.code:22:11: note: declared here
   22 | const int N = 205;
      |           ^
answer.code:36:7: error: invalid use of non-static data member ‘Dinic::N’
   36 | int d[N];            // 从起点到i的距离
      |       ^
answer.code:22:11: note: declared here
   22 | const int N = 205;
      |           ^
answer.code:37:9: error: invalid use of non-static data member ‘Dinic::N’
   37 | int cur[N];          // 当前弧指针
      |         ^
answer.code:22:11: note: declared here
   22 | const int N = 205;
      |           ^
answer.code:23:17: warning: overflow in conversion from ‘long long int’ to ‘int’ changes value from ‘9223372036854775807’ to ‘-1’ [-Woverflow]
   23 | const int inf = LONG_LONG_MAX;
      |                 ^~~~~~~~~~~~~
answer.code: In member function ‘void Dinic::init(int)’:
answer.code:41:33: error: ‘G’ was not declared in this scope
   41 |     for (int i = 0; i < n; i++) G[i].clear();
      |                                 ^
answer.code: In member function ‘void Dinic::add(int, int, int)’:
answer.code:49:5: error: ‘G’ was not declared in this scope
   49 |     G[from].push_back(m - 2);
      |     ^
answer.code: In member function ‘bool Dinic::BFS()’:
answer.code:54:12: error: ‘vis’ was not declared in this scope; did you mean ‘vi’?
   54 |     memset(vis, 0, sizeof(int) * n);
      |            ^~~
      |            vi
answer.code:58:5: error: ‘d’ was not declared in this scope; did you mean ‘db’?
   58 |     d[s] = 0;
      |     ^
      |     db
answer.code:62:29: error: ‘G’ was not declared in this scope
   62 |         for (int i = 0; i < G[x].size(); i++) {
      |                             ^
answer.code: In member function ‘int Dinic::DFS(int, int)’:
answer.code:77:19: error: ‘cur’ was not declared in this scope
   77 |     for (int &i = cur[x]; i < G[x].size(); i++) {
      |                   ^~~
answer.code:77:31: error: ‘G’ was not declared in this scope
   77 |     for (int &i = cur[x]; i < G[x].size(); i++) {
      |                               ^
answer.code:79:13: error: ‘d’ was not declared in this scope; did you mean ‘db’?
   79 |         if (d[x] + 1 == d[e.to] &&
      |             ^
      |             db
answer.code: In member function ‘int Dinic::Maxflow(int, int)’:
answer.code:95:16: error: ‘cur’ was not declared in this scope
   95 |         memset(cur, 0, sizeof(int) * n);
      |                ^~~