在做 HDU 4307 时,我使用 Dinic 求解网络流,在 dfs 上使用我自己的写法会 TLE,将其换成题解的写法即可 AC。
请问这两种写法有什么差异?以及 TLE 是常数问题还是死循环等错误?
我自己的写法:
int dfs(int u, int fl) {
if (u == ed) return fl;
int res = 0;
for (int i = now[u]; ~i; i = E[i].nxt) {
now[u] = i;
int v = E[i].v, w = E[i].w;
if (d[v] != d[u] + 1 || w <= 0) continue;
int nowf = dfs(v, min(fl, w));
E[i].w -= nowf;
E[i ^ 1].w += nowf;
fl -= nowf;
res += nowf;
}
if (!res) d[u] = -1;
return res;
}
int work() {
int ans = 0;
while (bfs()) {
for (int i = 0; i <= ed; i++) now[i] = head[i];
// memcpy(now, head, sizeof(now));
ans += dfs(st, 0x3f3f3f3f);
}
return ans;
}
题解里的写法:
int dfs(int u,int exp)
{
if(u==ed)return exp;
int v;int tmp;
for(int i=now[u];~i;i=E[i].nxt)
{ now[u]=i;
v=E[i].v;
if(E[i].w&&d[v]==d[u]+1&&(tmp=dfs(v,min(exp,E[i].w)))>0)
{
E[i].w-=tmp;E[i^1].w+=tmp;return tmp;
}
}
return 0;
}
int dinic_flow()
{
int sum=0,data;
while(bfs())
{
for(int i=0;i<=ed;++i)now[i]=head[i];
while(data=dfs(st,INF))sum+=data;
}
return sum;
}