RT,刚学,仿着dinic写的,不懂为什么一直错。求教
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i = a;i <= b;i ++)
#define per(i,a,b) for(int i = b;i >= a;i --)
using namespace std;
const int mm = 1e4+10;
const int nn = 5e2+10;
const ll inf = 1e18;
struct edge
{
ll v,nt,w,fl;
}e[mm<<1];
int ecnt,h[nn],cur[nn];
void add(ll u,ll v,ll w)
{
e[++ecnt] = {v,h[u],w,0};
h[u] = ecnt;
}
int hs(int x)
{
int tmp = x & 1 ? 1 : -1;
return x + tmp;
}
int dep[nn],gap[nn];
int S,T,n,m;
void bfs()
{
queue<int> q;
rep(i,1,n) dep[i] = -1;
// dep[T] = 1;gap[1] = 1;
dep[T] = 0;gap[0] = 1;
q.push(T);
while(!q.empty())
{
int x = q.front();q.pop();
for(int i = h[x];i;i = e[i].nt)
{
int y = e[i].v;
if(dep[y] != -1) continue;
q.push(y);
// cout << y << " " << x << "\n";
dep[y] = dep[x] + 1;
gap[dep[y]]++;
}
}
// rep(i,1,n) cout << dep[i] << " ";cout << "\n";
// rep(i,1,n) cout << gap[i] << " ";cout << "\n";
}
ll ans,max_flow;
ll dfs(int x,ll flow)
{
if(x == T || flow == 0)
{
ans += flow;
return flow;
}
ll ret = 0;
for(int i = h[x];i;i = e[i].nt)
{
int y = e[i].v;
ll tmp = 0;
if((e[i].w - e[i].fl > 0)&&( tmp = dfs(y,min(flow - ret,e[i].w - e[i].fl))) && dep[y] + 1 == dep[x])
{
e[i].fl += tmp;
e[hs(i)].fl -= tmp;
ret += tmp;
if(ret == flow) return ret;
}
}
// cout << x << " " << T << " " << ret << "\n";
--gap[dep[x]];
if(!gap[dep[x]]) dep[S] = n + 1;
dep[x] ++;
gap[dep[x]] ++;
return ret;
}
void ISAP()
{
bfs();
// rep(i,1,n) cout << "dep:" << dep[i] << " " << i << "\n";
int time = 0;
while(dep[S] < n) dfs(S,inf);
// cout <<"time:" << ++time << "\n";
cout << ans << "\n";
}
void mian()
{
cin >> n >> m >> S >> T;
int x,y;ll z;
rep(i,1,m) cin >> x >> y >> z,add(x,y,z),add(y,x,0);
ISAP();
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
// rep(i,1,5) cout << i << hs(i) << "\n";
mian();
return 0;
}