MINO1 @ 2024-10-01 23:41:13
这是oi wiki上的Dinic模板,一个月前,我把dfs中的e[i^1].flow改成了e[i|1].flow,仍然ac了这个模板题。
直到遇到codeforces 976F,被改这一下害惨了,搞了好久都没ac,因为都忘记改过了,还以为是思路有问题,看了好久才发现是模板有问题。
欢迎来hack本蒟蒻。
//code by MINO1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 10004;
const int INF = INT_MAX;
struct MF {
struct edge {
int v,nxt,cap,flow;//子节点,下一条边,容量,流量
} e[N];
int fir[N],cnt = 0;
int n,S,T;
ll maxflow = 0;
int dep[N],cur[N];
void init(int n,int s,int t) {
cnt = 0;maxflow = 0;
this->n = n;this->S = s;this->T = t;
memset(fir,-1,sizeof(int) * (n + 1));
}
void addedge(int u,int v,int w) {
e[cnt] = {v,fir[u],w,0};
fir[u] = cnt++;
e[cnt] = {u,fir[v],0,0};
fir[v] = cnt++;
}
bool bfs() {
queue<int> q;
memset(dep,0,sizeof(int) * (n + 1));
dep[S] = 1;
q.push(S);
while (q.size()) {
int u = q.front();
q.pop();
for (int i = fir[u];~i;i = e[i].nxt) {
int v = e[i].v;
if (!dep[v] && e[i].cap > e[i].flow) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[T];
}
int dfs(int u,int flow) {
if (u == T || !flow) return flow;
int ret = 0;
for (int& i = cur[u];~i;i = e[i].nxt) {
int v = e[i].v;int d = 0;
if (dep[v] == dep[u] + 1 && (d = dfs(v,min(flow - ret,e[i].cap - e[i].flow)))) {
ret += d;
e[i].flow += d;
e[i | 1].flow -= d;
if (ret == flow) return ret;
}
}
return ret;
}
ll dinic() {
while (bfs()) {
memcpy(cur,fir,sizeof(int) * (n + 1));
maxflow += dfs(S,INF);
}
return maxflow;
}
}mf;
void solve() {
int n,m,s,t;cin >> n >> m >> s >> t;
mf.init(n,s,t);
for (int i = 1;i <= m;i++) {
int u,v,w;cin >> u >> v >> w;
mf.addedge(u,v,w);
}
cout << mf.dinic() << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
}
by EasonLiang @ 2024-10-02 00:05:57
乐
by Terrible @ 2024-10-02 00:40:05
意义不大的行为:“打破砂锅问到底”,解析一下题目目前采用的数据,考察错误情况并总结数据的某种性质。
有意义的目的:加点数据卡掉错误代码,以防后人再次掉坑。
问“为什么”要么是不清楚自己能从中得到什么,要么是表达中掩盖了一定的目的性。
为什么对个人意义不大?这会费时费力总结出来一些普遍性不是很强的结论,而且这对参加赛事来说也大可不必。
by _Ad_Astra_ @ 2024-10-02 00:48:23
@MINO1 说明数据太弱,反向边没用到过。
by Terrible @ 2024-10-02 01:04:54
洛谷很多数据都很水,而且似乎没人修的样子。
本题后面就补加了一个新测试点,真就挤牙膏呗?
by lonely_seele @ 2024-10-02 01:30:07
@Terrible 意义较大的行为:告诉大家这题数据过弱,如果你通过了这到模板题仍然需要检查自己板子的什么地方
意义微小的行为:在这个帖子下面批判楼主(当然我这条回复也是)