QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#756209 | #143. 最大流(随机数据) | Vegetable_Dog | Compile Error | / | / | C++23 | 3.0kb | 2024-11-16 19:21:59 | 2024-11-16 19:21:59 |
Judging History
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;
}
详细
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); | ^~~