关于 Dinic 的 dfs 两种写法的疑问
  • 板块学术版
  • 楼主tribool4_in
  • 当前回复12
  • 已保存回复12
  • 发布时间2023/7/31 23:08
  • 上次更新2023/11/3 06:39:45
查看原帖
关于 Dinic 的 dfs 两种写法的疑问
341650
tribool4_in楼主2023/7/31 23:08

在做 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;
}
2023/7/31 23:08
加载中...