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

 
 
 
日一二三四五六
       
       
       
       
       
       

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

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

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
11月15日漏签0天
noip吧 关注:25,184贴子:642,064
  • 看贴

  • 图片

  • 吧主推荐

  • 视频

  • 游戏

  • 5回复贴,共1页
<<返回noip吧
>0< 加载中...

跪求大牛帮我Dinic查下错!

  • 只看楼主
  • 收藏

  • 回复
  • pkqs90
  • 提高一等
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
前几天学了dinic,本来想写poj1273的,不过discuss里有组数据过不去。。我查了快俩小时了。。实在不知道哪错了。。跪求大牛帮我看看
(我觉得我的reverse那块有问题。。不过不是特别确定= =。。跪求大牛帮忙啊啊)
#include<iostream>
#include<fstream>
#define Inf 0x7fffffff
using namespace std;
ifstream fin("1.txt");
int n,cnt,first[1005],level[1005],ans=0;
struct edge
{
        int next,pnt,remain,reverse;
}e[10005];
void Addedge(int x,int y,int z)
{
     e[++cnt].next=first[x];
     first[x]=cnt;
     e[cnt].pnt=y;
     e[cnt].remain=z;
     e[cnt].reverse=cnt+1;
     e[++cnt].next=first[y];
     first[y]=cnt;
     e[cnt].pnt=x;
     e[cnt].remain=0;
     e[cnt].reverse=cnt-1;
}
bool makelevel()
{
      for(int i=1;i<=n;i++)
         level[i]=-1;
      int p=0,q=1,queue[1005];
      queue[1]=1;level[1]=0;
      while(p<q)
      {
         p++;
         for(int i=first[queue[p]];i;i=e[i].next)
            if(e[i].remain&&level[e[i].pnt]<0)
               level[queue[++q]=e[i].pnt]=level[queue[p]]+1;
      }
      return level[n]>=0;
}
int MAXflow(int s,int flow)
{
     if(s==n)return flow;
     int maxflow=0,d;
     for(int i=first[s];i;i=e[i].next)
     {
        if(level[e[i].pnt]==level[s]+1)
        {
           d=MAXflow(e[i].pnt,min(flow,e[i].remain));
           if(d>0)
           {
              maxflow+=d;
              e[i].remain-=d;
              if(e[i].reverse)
                 e[i].reverse+=d;
           }
        }
     }
     if(!maxflow)level[s]=-1;
     return maxflow;
}
          
void Dinic()
{
     int d;
     while(makelevel())
        if(d=MAXflow(1,Inf))
           ans+=d;
}
int main()
{
     int m,i,j,s,t,x,y,z;
     while(fin>>m>>n){
        ans=0;cnt=0;
        memset(first,0,sizeof(first));
        while(m--)
        {
           fin>>x>>y>>z;
           Addedge(x,y,z);
        }
        Dinic();
        cout<<ans<<endl;
     }
     system("pause");
     return 0;
}



  • pkqs90
  • 提高一等
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
9 6
1 2 10
1 3 10
2 3 2
2 4 4
2 5 8
3 5 9
5 4 6
4 6 10
5 6 10
这是那组死也过不去的数据。。哭了。。


2025-11-15 15:09:06
广告
不感兴趣
开通SVIP免广告
  • 广陵lonely散
  • 怒进省队
    9
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
回复:2楼
这是Dinic吗???


  • WJMZBMR
  • NOI银牌
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

              maxflow+=d;
              e[i].remain-=d;
              if(e[i].reverse)
                 e[i].reverse+=d;
。。。。。囧。。。


  • sliverwxj
  • 省选酱油
    8
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
回复:2楼
   d=MAXflow(e[i].pnt,min(flow,e[i].remain));
           if(d>0)
           {
              maxflow+=d;
              e[i].remain-=d;
………………………………………………这里你貌似没有把flow也减少d
              if(e[i].reverse)
                 e[i].reverse+=d;
           }
        }
     }
不大熟悉c++,这里应该是问题之一吧
回复:3楼
是吧。。。


  • pkqs90
  • 提高一等
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
啊!刚才又调了调,发现自己犯脑残了!!
6L最大的错误就是吧reverse的边给去了!
终于用dinic0msac掉1273。。感觉真不是一个爽字了得啊


登录百度账号

扫二维码下载贴吧客户端

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