求助dnic板子

迟暮天复明 @ 2025-04-12 22:45:38

struct edge{
  int to,nxt,flow;
}e[200010];
int cnt=1,head[200010],now[200010],dep[200010],n,m,s,t;
void add(int u,int v,int w){
//  cout<<u<<' '<<v<<' '<<w<<endl;
  e[++cnt]={v,head[u],w};
  head[u]=cnt;
  e[++cnt]={u,head[v],0};
  head[v]=cnt;
}
int bfs(){
  for(int i=0;i<=t;++i)dep[i]=0,now[i]=head[i];dep[s]=1;
  queue<int>q;q.push(s);
  while(!q.empty()){
    int u=q.front();q.pop();
    for(int i=head[u];i;i=e[i].nxt){
      int v=e[i].to;if(e[i].flow>0&&dep[v]==0){
        dep[v]=dep[u]+1,q.push(v);
        if(v==t)return 1;
      }
    }
  }return 0;
}
int dfs(int u,int f){
  if(u==t||!f)return f;
  int sum=0;
  for(int &i=now[u];i;i=e[i].nxt){
    int v=e[i].to;
    if(e[i].flow)
    if(dep[v]==dep[u]+1){
      int k=dfs(v,min(f,e[i].flow));
      if(!k){dep[v]=0;continue;}
      e[i].flow-=k,e[i^1].flow+=k;
      sum+=k,f-=k;
    }
  }return sum;
}
bool check(int k){
  memset(e,0,sizeof(e));
  for(int i=1;i<=t;++i)head[i]=now[i]=dep[i]=0;
  cnt=1;
  for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if(F[i][j]<=k){
    add(i,j+n,1);
  }
  for(int i=1;i<=n;++i)add(s,i,1);
  for(int i=1;i<=n;++i)add(i+n,t,1);
  int ans=0;while(bfs())ans+=dfs(s,INT_MAX);
//  cout<<k<<' '<<ans<<endl;

  return ans==n;
}

by Idtwtei @ 2025-04-12 22:51:40

@迟暮天复明

for(int &i=now[u];i;i=e[i].nxt){ 

应该加个 f != 0？

by mywwzh @ 2025-04-12 22:59:06

@迟暮天复明

link，不知道对不对。

by Sublimity @ 2025-04-12 22:59:53

应该在第二位加一个 i

by syzf2222 @ 2025-04-12 23:11:31

我觉得你没写错

by Idtwtei @ 2025-04-13 00:16:59

@迟暮天复明

自己试了一下，应该就是我提的问题。

当 f 为 0 时，遍历接下来的节点出去的流量都为 0，那么你会使得遍历过的节点 dep=0，此时其他点在遍历就因为 dep 错误而失败。

将 dep=0 删去后得到的增广轮数是对的。

by minstdfx @ 2025-04-13 00:57:46

Scarlet.: 04-12 22:53:17
当前弧优化分为两个部分，一是维护到某个下标之前的所有边都被榨干了
所以第一个部分需要在访问到边的时候维护，而不是&i=cur[u]
但是你写的是当这个边有流量的时候才更新cur，这会导致比如说你这次访问到这个点的时候边指针指向上一个有流量的边，但是可能这条边已经干了，并且后面的边都已经干了

Scarlet.: 04-12 22:53:22
这是第一个问题

Scarlet.: 04-12 22:54:00
第二部分是，当f不等于0的时候要及时退出循环，否则你相当于一直在更新cur，而不考虑前面是否有没流满的边，这样就导致退化成ek

Scarlet.: 04-12 22:54:25
而写 int &i=cur[u];i;i=e[i].nxt的后果和第二条是一样的

Scarlet.: 04-12 22:54:38
@1358id

1358id: 04-12 22:55:11
这么厉害

Scarlet.: 04-12 22:55:12
而第一行的diff其实无所谓

Scarlet.: 04-12 22:55:35
更新cur，循环到i说明u点已经用到了第i条边，也说明前i-1条边已经被榨干了（所以才用到了第i条边），因此下次直接从u点用第i条边就可以了，所以cur[u]更新为i就可以了

Scarlet.: 04-12 22:56:18
额哪里没听懂可能是我讲得不好，我详细解释一下(

1358id: 04-12 22:57:06
&i=now[u]是不是和你的写法没有本质区别来着

1358id: 04-12 22:57:09
我ac了

Scarlet.: 04-12 22:57:20
@1358id 有区别的

Scarlet.: 04-12 22:57:30
&i=now[u]是错的

1358id: 04-12 22:59:03
为啥

1358id: 04-12 22:59:05
不懂

Scarlet.: 04-12 22:59:28
因为你这么写相当于你遇到了流不满的边会“执行一次loop-updation”再执行i&&f的loop-condition-check

Scarlet.: 04-12 22:59:53
执行一次loop-updation的结果就是cur[u]会指向流不满的边的下一条

Scarlet.: 04-12 22:59:59
和当前弧优化的定义不符

Scarlet.: 04-12 23:00:05
然后退化成ek

Scarlet.: 04-12 23:02:02
@1358id 

1358id: 04-12 23:02:30
我看不懂。

Scarlet.: 04-12 23:02:45
就比如说

Scarlet.: 04-12 23:03:01
嗯

Scarlet.: 04-12 23:03:22
比如说你到第二条边你这个点的流量被榨干了，但是第二条没跑满

Scarlet.: 04-12 23:03:31
按照我的写法会继续指向第二条边

Scarlet.: 04-12 23:03:50
按引用的错误写法就指向第三条了

1358id: 04-12 23:03:59
哦

1358id: 04-12 23:04:07
牛的

Scarlet.: 04-12 23:04:09
这样的话，下一次找到这个点就会从第二条便继续流

Scarlet.: 04-12 23:04:16
否则就，相当于没流干

Scarlet.: 04-12 23:04:27
那就不符合我们证明dinic复杂度时候的前提

Scarlet.: 04-12 23:04:32
就会退化成ek

by minstdfx @ 2025-04-13 01:03:42

补充：在单位容量网络不存在流一半的情况，所以&i的写法可能对的，但也要加上i&&f。事实证明，加上之后就过了

by Idtwtei @ 2025-04-13 01:13:36

@minstdfx

在单位网络的条件下，第一部分还有问题吗？

by minstdfx @ 2025-04-13 01:14:15

@Idtwtei 感觉可能没有，但是最好别那么写。

by Idtwtei @ 2025-04-13 01:14:50

@minstdfx

我提的问题确实是你的第二部分吧。