这份代码在本地编译的时候抛出了Segmentation Fault,但在洛谷评测机上通过,求问原因。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
class edge{
public:
edge(int l, int r, ll v){
this->l = l; this->r = r; this->val = v;
}
int l, r;
ll val;
};
class graph{
public:
graph(int _max_node = 0, int st = 0, int en = 0){
ecn = 0;
max_node = _max_node; t = en; s = st;
for(int i = 1; i <= max_node; i++){
nodes[i] = vector<int>();
}
}
vector<int> get_outer_edge(int node_id){
return nodes[node_id];
}
edge& get_edge(int edge_id){
return alle[edge_id];
}
pair<int, int> get_s_and_t(){
return make_pair(s, t);
}
int get_max_node(){
return max_node;
}
void add_edge_direction(int l, int r, ll k){
alle.push_back(edge(l, r, k));
nodes[l].push_back(ecn);
ecn++;
}
void add_edge_binary(int l, int r, ll k){
add_edge_direction(l, r, k);
add_edge_direction(r, l, 0);
}
private:
int ecn, s, t, max_node;
vector<edge> alle;
vector<int> nodes[210000];
};
class dinic{
public:
dinic(graph G){
this->G = G;
}
ll max_flow(){
ll ans = 0;
while(bfs()) ans += dfs(G.get_s_and_t().first, inf);
return ans;
}
private:
graph G;
queue<int> bfs_q;
const int inf = 2045141919;
int depth[240000], cur[240000];
int bfs(){
for(int i = 1; i <= G.get_max_node(); i++){
depth[i] = 0;
cur[i] = 0;
}
bfs_q.push(G.get_s_and_t().first);
depth[G.get_s_and_t().first] = 1;
while(bfs_q.size()){
int now_node = bfs_q.front();
bfs_q.pop();
vector<int> outer = G.get_outer_edge(now_node);
for(int i = 0; i < outer.size(); i++){
edge e = G.get_edge(outer[i]);
if(e.val > 0 && !depth[e.r]){
bfs_q.push(e.r);
depth[e.r] = depth[e.l] + 1;
}
}
}
return depth[G.get_s_and_t().second];
}
ll dfs(int now_node, ll flow){
if(now_node == G.get_s_and_t().second){
return flow;
}
ll used = 0;
vector<int> outer = G.get_outer_edge(now_node);
for(int i = cur[now_node]; i < outer.size(); i++){
cur[now_node] = i;
edge& e = G.get_edge(outer[i]);
if(!e.val || depth[e.r] - depth[e.l] != 1) continue;
ll next_flow = dfs(e.r, min(e.val, flow - used));
if(!next_flow){
depth[e.r] = -1;
continue;
}
e.val -= next_flow;
G.get_edge(outer[i] ^ 1).val += next_flow;
used += next_flow;
if(used == flow){
return flow;
}
}
return used;
}
};
class block{
public:
ll x, y, cost;
block(int _x = 0, int _y = 0, int _cost = 0) : x(_x), y(_y), cost(_cost){}
}bl[110000];
int n, m, l, r, X, Y, s, t, b, dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int k, inf = 2045141919;
map<pair<int, int>, int> mp;
int get_color(int x, int y){
if(y % 2 == 1) return x % 4 + 1;
if(x % 2 == 1) return x % 4;
return x % 4 + 2;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
graph G = graph(0, 0, 0);
cin >> X >> Y >> b;
s = b * 2 + 1, t = s + 1;
G = graph(t, s, t);
for(int i = 1; i <= b; i++){
cin >> l >> r >> k;
bl[i] = block(l, r, k);
mp[{l, r}] = i;
}
for(int i = 1; i <= b; i++){
int col = get_color(bl[i].x, bl[i].y);
G.add_edge_binary(i, i + b, bl[i].cost);
if(col == 1) G.add_edge_binary(s, i, inf);
if(col == 4) {G.add_edge_binary(i + b, t, inf); continue;}
for(int j = 0; j < 4; j++){
int nx = bl[i].x + dir[j][0], ny = bl[i].y + dir[j][1];
if(nx < 1 || nx > X || ny < 1 || ny > Y) continue;
if(mp[{nx,ny}] == 0) continue;
int new_col = get_color(nx, ny);
if(col + 1 == new_col) G.add_edge_binary(i + b, mp[{nx, ny}], inf);
}
}
dinic d(G);
cout << d.max_flow();
return 0;
}
编译条件如下(VSCode):
{
"C_Cpp.intelliSenseEngine": "disabled",
"clangd.arguments": [
"--header-insertion=never",
"--query-driver=D:/mingw64/bin/g++.exe",
"-j=6"
],
"clangd.fallbackFlags": [
"-Wall",
"-Wextra",
"-std=c++2a",
"--target=x86_64-pc-windows-gnu",
"g++ paths.cpp –o paths –Wl,--stack=268435456 –O2 "
],
"c-cpp-compile-run.cpp-flags": "-Wall -Wextra -g3 -std=c++2a",
"editor.fontSize": 18
}