网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索

 
 
 
日一二三四五六
       
       
       
       
       
       

签到排名:今日本吧第个签到,

本吧因你更精彩,明天继续来努力!

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
06月02日漏签0天
c++吧 关注:617,467贴子:2,111,094
  • 看贴

  • 图片

  • 吧主推荐

  • 游戏

  • 28回复贴,共1页
<<返回c++吧
>0< 加载中...

蒟蒻求助dinic算法的问题

  • 只看楼主
  • 收藏

  • 回复
  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
我的dinic出了一个小错,我觉得应该是bfs或者是存边出了问题,请大佬指点一二,鄙人不胜感激


  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
const int maxm=100005;
const int INF=0x7f7f7f;
int n,m,s,t,cnt=-1;
int head[maxn],dep[maxn];
struct node{
int to,cc,nex;
}edge[maxm*2];
void add_edge(int a,int b,int c)
{
edge[++cnt].nex=head[a];
edge[cnt].to=b;
edge[cnt].cc=c;
head[a]=cnt;
}
void add(int a,int b,int c)
{
add_edge(a,b, c);
add_edge(b,a,0);
}
int dfs(int u,int strm)
{
cout<<"dfs"<<" u:"<<u<<" strm:"<<strm<<endl;
if(u==t) return strm;
for(int i=head[u];i!=-1;i=edge[i].nex)
{
if(edge[i].cc && dep[edge[i].to]==dep[u]+1)
{
int d=dfs(edge[i].to,min(strm,edge[i].cc));
if(d>0)
{
edge[i].cc-=d;
edge[i^1].cc+=d;
return d;
}
}
}
return 0;
}
bool bfs()
{
cout<<"bfs"<<endl;
queue<int>q;
while(!q.empty())
q.pop();
memset(dep,-1,sizeof(dep));
dep[s]=0;
q.push(s);
do
{
int u=q.front();
cout<<"u:"<<u<<endl;
q.pop();
for(int i=head[u];i!=-1;i=edge[i].nex)
{
cout<<"v:"<<edge[i].to<<endl;
if(edge[i].cc>0 && dep[edge[i].to]==-1)
{
dep[edge[i].to]=dep[u]+1;
q.push(edge[i].to);
}
}
}
while(!q.empty());
if(dep[t]==-1) return false;
return true;
}
int dinic()
{
int ans=0;
while(bfs())
{
while(int d=dfs(s,INF))
ans+=d;
}
return ans;
}
int main()
{
freopen("input.txt","r",stdin);
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;++i)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
printf("%d",dinic());
return 0;
}


2025-06-02 17:42:38
广告
  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
是luogu上面的最大流模版题


  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
是看了这一个大佬的blog
https://www.cnblogs.com/SYCstudio/p/7260613.html


  • 奶粉452
  • |
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
那个题目里面,4213为什么不是30?大佬我没看懂题


  • 奶粉452
  • |
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
就是这个图里面,他说4213只能通过10流量,不是应该30流量吗?


  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼



  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
极度怀疑是bfs或者存图模块出错
望大佬指点


2025-06-02 17:36:38
广告
  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
没有人吗。。。嘤嘤嘤,我去吃饭了


  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
睡了一个午觉还是没有人回复我


  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
我***是个瓜皮


  • Kari咖喱
  • &&
    6
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
原来是scanf的格式少打了一个%d


  • 西塞罗神
  • <<
    12
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
dinic加个当前弧优化会比较好,听说有题可能会卡这个?


登录百度账号

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频!
  • 贴吧页面意见反馈
  • 违规贴吧举报反馈通道
  • 贴吧违规信息处理公示
  • 28回复贴,共1页
<<返回c++吧
分享到:
©2025 Baidu贴吧协议|隐私政策|吧主制度|意见反馈|网络谣言警示