Night_Bringer @ 2020-12-04 13:05:32
题解就一共跑了几十毫秒,我最慢的就有一秒多
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define Min(a, b) ((a) < (b) ? (a) : (b))
void Quick_Read(LL &N) {
N = 0;
LL op = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
op = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
N = (N << 1) + (N << 3) + (c ^ 48);
c = getchar();
}
N *= op;
}
const LL MAXN = 2e2 + 5;
struct Node {
LL to, value, rev;
Node() {}
Node(LL T, LL V, LL R) {
to = T;
value = V;
rev = R;
}
};
vector<Node> v[MAXN];
queue<LL> q;
LL de[MAXN], be[MAXN];
LL n, m, s, t;
bool bfs_Dinic() {
memset(de, 0, sizeof(de));
while(!q.empty())
q.pop();
q.push(s);
de[s] = 1; be[s] = 0;
while(!q.empty()) {
LL now = q.front();
q.pop();
LL SIZ = v[now].size();
for(int i = 0; i < SIZ; i++) {
LL next = v[now][i].to;
if(v[now][i].value && !de[next]) {
q.push(next);
be[next] = 0;
de[next] = de[now] + 1;
if(next == t)
return true;
}
}
}
return false;
}
LL dfs_Dinic(LL now, LL flow) {
if(now == t)
return flow;
int i, surp = flow;
LL SIZ = v[now].size();
for(i = be[now]; i < SIZ && surp; i++) {
LL next = v[now][i].to, valedge = v[now][i].value;
if(valedge && de[next] == de[now] + 1) {
LL maxnow = dfs_Dinic(next, Min(surp, valedge));
if(!maxnow)
de[next] = 0;
v[now][i].value -= maxnow;
v[next][v[now][i].rev].value += maxnow;
surp -= maxnow;
}
}
be[now] = i;
return flow - surp;
}
LL Dinic() {
LL res = 0, flow = 0;
while(bfs_Dinic())
while(flow = dfs_Dinic(s, INF))
res += flow;
return res;
}
void Read() {
LL A, B, C;
Quick_Read(n);
Quick_Read(m);
Quick_Read(s);
Quick_Read(t);
for(int i = 1; i <= m; i++) {
Quick_Read(A);
Quick_Read(B);
Quick_Read(C);
LL idA = v[A].size(), idB = v[B].size();
v[A].push_back(Node(B, C, idB));
v[B].push_back(Node(A, 0, idA));
}
}
int main() {
Read();
printf("%lld", Dinic());
return 0;
}
by Night_Bringer @ 2020-12-04 13:54:45
问题解决了,谢谢回答我的大佬们