已经过题,但是时间比其他选手的劣很多。
希望能帮忙看一下,谢谢。
参考提交(别人的,总共59ms):https://www.luogu.com.cn/record/67846830
我的代码(总共279ms):
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define go(i,a) for(int i=cur[a];i;i=edge[i].nxt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
const int N = 5005;
const int INF = 2e9;
int n, m;
struct nod {
int y, nxt;
int c;
}edge[N<<2];
int el = 1;
int Edgehead[N];
int dis[205];
int cur[205];
int S, T;
int q[205], head, tail;
void add (int x, int y, ll c) {
el++;
edge[el].y = y, edge[el].c = c, edge[el].nxt = Edgehead[x], Edgehead[x] = el;
return;
}
void ins (int x, int y, ll c) {
add (x, y, c);
add (y, x, 0ll);
return;
}
bool bfs () {
mem (dis, -1);
dis[S] = 0;
q[head = 1] = S, tail = 2;
while (head < tail) {
int x = q[head++];
cur[x] = 0;
for (int i = Edgehead[x]; i; i = edge[i].nxt) {
int y = edge[i].y;
if (edge[i].c && dis[y] == -1) {
if (!cur[x]) cur[x] = i;
dis[y] = dis[x] + 1;
q[tail++] = y;
}
}
}
return dis[T] != -1;
}
int dfs (int k, int flow) {
if (k==T || !flow) return flow;
int have = 0;
go (i,k) {
int y=edge[i].y;
if (dis[y] == dis[k]+1 && edge[i].c) {
int back = dfs (y, min(flow-have, edge[i].c));
have += back;
edge[i].c -= back;
edge[i^1].c += back;
if (have == flow)return flow;
}
cur[k] = edge[i].nxt;
}
dis[k] = -1;
return have;
}
int main () {
// freopen ("3376.in", "r", stdin);
mem (Edgehead, 0);
scanf ("%d %d %d %d", &n, &m, &S, &T);
fo (i,1,m) {
int x, y, c;
scanf ("%d %d %d", &x, &y, &c);
ins (x, y, c);
}
ll ans = 0;
while (bfs ()) {
ans += dfs (S, INF);
}
printf ("%lld\n", ans);
return 0;
}