70分求助

P3376 【模板】网络最大流

walk_alone @ 2018-08-07 17:39:36

发现一个很神奇的现象: 在dfs函数中如果加入参数t(终点),那么就可以过第三个点,但是其他的都死循环里过不了。打印出来看,发现这个t一直都在变(难道可以变吗?)。但如果不加参数就一直七十分。求助。

#include <cstdio>
#include <algorithm>
using namespace std;
const int inf=999999999;
struct node
{
    int from;
    int to;
    int v;
    int next;
};
struct node que[300001];
int head=1,tail=2,headers[100001],book[100001],place[100001],depth[100001],s,t,n,m;
bool bfs()
{
    for(int i=1;i<tail;i++)
        place[i]=depth[i]=book[i]=0;
    head=1;
    tail=2;
    place[head]=s;
    depth[s]=1;
    book[place[head]]=1;
    while(head<tail)
    {
        for(int t=headers[place[head]];t;t=que[t].next)
            if(que[t].v>0 && book[que[t].to]==0)
            {
                place[tail]=que[t].to;
                depth[que[t].to]=depth[place[head]]+1;
                book[que[t].to]=1;
                tail++;
            }
        head++;
    }
    if(depth[t]==0)
        return 0;
    return 1;
}
int dfs(int u,int dis)
{
    if(u==t)
        return dis;
    for(int t=headers[u];t;t=que[t].next)
        if(depth[que[t].to]==depth[u]+1 && que[t].v>0)
        {
            int d=dfs(que[t].to,min(dis,que[t].v));
            if(d>0)
            {
                que[t].v-=d;
                que[t^1].v+=d;
                return d;
            }
        }
    return 0;
}
int dinic(int s,int t)
{
    int ans=0;
    while(bfs())
        while(int d=dfs(s,inf))
            ans+=d;
    return ans;
}
int main()
{
    int count=1,a,b,c;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        que[count].from=a;
        que[count].to=b;
        que[count].v=c;
        que[count].next=headers[a];
        headers[a]=count;
        count++;
        que[count].from=b;
        que[count].to=a;
        que[count].next=headers[b];
        headers[b]=count;
        count++;
    }
    printf("%d",dinic(s,t));
    return 0;
}

by Soulist @ 2018-08-07 17:48:27

您的t当然一直在变啊,变量名推荐写的大众一点 此处: for(int t=headers[u]; t ; t = que[t].next) t的值固然会改变啊


by Soulist @ 2018-08-07 17:48:44

您写出i之类的应该就没事了


by Soulist @ 2018-08-07 17:50:20

特别好奇您是怎么拿70分的%%%


by walk_alone @ 2018-08-07 20:39:46

@Hakuryu_CYZ 突然发现我智障了。还是感谢神仙。


by Soulist @ 2018-08-07 20:52:13

@walk_alone 我是蒟蒻QWQ


by walk_alone @ 2018-08-07 21:00:26

@Hakuryu_CYZ 好了也不扯这个事,但问题是现在改过来还是70,但是没那个加不加参数的问题了。重边的问题也考虑了,但为什么又只有60?


by Soulist @ 2018-08-07 21:43:46

@walk_alone 洛谷的消息延时好大QWQ

(一直泡在小号上写题233)

推荐您把手写的队列改成STL,之前我写网络流的时候反正手写的队列就是过不了233

以及,网络因为cnt是从0开始计数的,所以在对边进行访问的时候不能写:

for(int i = head[x]; i; i = e[i].next)

这样的QWQ,主要是i = 0有两种情况,1是第一条边,2是终止条件

所以我一般都是用-1或者讲cnt初始化为2

以及,您是把所有循环中的t都改过来了吗? bfs里面也有t


by Soulist @ 2018-08-07 21:44:38

对了,这道题数据超级水,这段代码有70分:

#include<bits/stdc++.h>
using namespace std;
int ans,n,m,u,v,w,s,t,minn;
int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        if(u == s) minn += w;
        if(v==t) 
            ans+=w;
    }
    cout<<min(minn, ans);
    return 0;
}

by Soulist @ 2018-08-07 21:48:50

@walk_alone 对了,您的cnt好像是从1开始的QWQ? 1^1 = 0且0^1 = 1来着如果我没记错 反正好像是如果要用x^1表示它的反向边,要从0开始计数,反正从偶数开始,抱歉,没注意到


by walk_alone @ 2018-08-07 22:21:49

@Hakuryu_CYZ 问题正是这里,感谢神仙,%%%。


| 下一页