SIXIANG32 @ 2021-06-01 21:48:58
又 WA 又 TLE 了，Dinic 磨人，救救孩子！/kk
#include <iostream>
#include <queue>
#include <cstring>
#define int long long
#define MAXN 100000
#define QWQ cout << "QWQ" << endl;
using namespace std;
int min(int x, int y) {return ((x < y) ? (x) : (y));}
struct node {
int id, val;
int next;
} gra[MAXN + 10];
int n, m, s, t;
int tot = 0, head[MAXN + 10], dis[MAXN + 10], Now[MAXN + 10];
void link(int x, int y, int z) {
gra[++tot].id = y, gra[tot].val = z;
gra[tot].next = head[x], head[x] = tot;
gra[++tot].id = x, gra[tot].val = 0;
gra[tot].next = head[y], head[y] = tot;
}
bool bfs() {
memset(dis, 0, sizeof(dis));
queue <int> que;
que.push(s), dis[s] = 1, Now[s] = head[s];
while(!que.empty()) {
int fr = que.front(); que.pop();
for(int p = head[fr]; p; p = gra[p].next) {
int v = gra[p].id, w = gra[p].val;
if(w && !dis[v]) {
que.push(v);
Now[v] = head[v];
dis[v] = dis[fr] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
int Dinic(int u, int over) {
if(u == t) return over;
int p, res = over, k;
for(p = Now[u]; p && res; p = gra[p].next) {
int v = gra[p].id, w = gra[p].val;
Now[u] = v;
if(w && dis[v] == dis[u] + 1) {
k = Dinic(v, min(res, w));
if(!k) dis[v] = 0x7f7f7f7f;
gra[p].val -= k;
gra[p ^ 1].val += k;
res -= k;
}
}
return over - res;
}
signed main() {
cin >> n >> m >> s >> t;
for(int p = 1, x, y, z; p <= m; p++) {
cin >> x >> y >> z;
link(x, y, z);
}
int maxn = 0, rest = 0;
while(bfs())
maxn += (rest = Dinic(s, 0x7f7f7f7f)), cout << rest << endl;
cout << maxn << endl;
}求助/kel
by Spasmodic @ 2021-06-01 22:02:05
学学当前弧？
by Stinger @ 2021-06-01 22:02:21
为啥这都要加反作弊啊/fad
by Stinger @ 2021-06-01 22:02:41
@happyChristmas 不是加了当前弧的吗（
by SIXIANG32 @ 2021-06-01 22:04:36
@zhangqs 啊不是是调试的
@happyChristmas 我加了啊，写假了吗？
by Spasmodic @ 2021-06-01 22:06:21
我瞎了，，
by Spasmodic @ 2021-06-01 22:08:56
不太清楚，你试试看改成最开始改 Now 数组
by SIXIANG32 @ 2021-06-01 22:10:46
@happyChristmas 啊咋改啊
我 bfs 的时候改过了啊
by Spasmodic @ 2021-06-01 22:20:08
@SIXIANG 就是在bfs前改
by SIXIANG32 @ 2021-06-01 22:22:41
@happyChristmas 咋改啊，全搞成 head 不行
by Spasmodic @ 2021-06-01 22:23:35
草，扔个我写的
namespace Dinic{
ll tot=1,hd[N],s,t,d[N],cur[N];
struct edge{ll t,c,nxt;}es[M<<1];
void add(ll u,ll v,ll c){
es[++tot]=(edge){v,c,hd[u]};hd[u]=tot;
es[++tot]=(edge){u,0,hd[v]};hd[v]=tot;
}
bool bfs(){
memset(d,0,sizeof(d));
queue<ll>q;
q.push(s);d[s]=1;
for(ll x;!q.empty();){
x=q.front();q.pop();
for(ll i=hd[x];i;i=es[i].nxt)
if(es[i].c&&!d[es[i].t]){
q.push(es[i].t);
d[es[i].t]=d[x]+1;
if(es[i].t==t)return 1;
}
}
return 0;
}
ll dinic(ll x,ll flow){
if(x==t)return flow;
ll k;
for(ll&i=cur[x];i;i=es[i].nxt)
if(es[i].c&&d[es[i].t]==d[x]+1){
k=dinic(es[i].t,min(flow,es[i].c));
if(k>0)return es[i].c-=k,es[i^1].c+=k,k;
}
return 0;
}
ll solve(){
ll ans=0;
for(ll flow;bfs();){
for(ll i=1;i<=n;i++)cur[i]=hd[i];
while((flow=dinic(s,INF)))ans+=flow;
}
return ans;
}
}