91分求助

zpl__hhd @ 2021-01-17 19:07:44

#include <bits/stdc++.h>
using namespace std;
const int maxn=210,maxm=5010;
int n,m,s,t,cnt=1;//注意cnt=1！！！！！
long long ans;
int head[maxn],cur[maxn],dis[maxn];
struct edge
{
    int t,next;
    long long f;
}e[maxm<<1];
void add(int f,int t,long long w)
{
    e[++cnt].f=w;
    e[cnt].t=t;
    e[cnt].next=head[f];
    head[f]=cnt;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    cur[s]=head[s];
    queue<int> q;
    q.push(s);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].next)
        {
            int v=e[i].t;
            if(e[i].f&&dis[v]==-1)
            {
                dis[v]=dis[x]+1;
                cur[v]=head[v];
                q.push(v);
            }
        }
    }
    return dis[t]!=-1;
}
long long dinic(int x,long long flow)
{
    if(x==t)return flow;
    long long tmp=flow;
    for(int i=cur[x];i;i=e[i].next)
    {
        cur[x]=i;
        int v=e[i].t;
        if(e[i].f&&dis[v]==dis[x]+1)
        {
            long long d=dinic(v,min(e[i].f,flow));
            if(d==0)dis[v]=INT_MAX;
            e[i].f-=d;
            e[i^1].f+=d;
            tmp-=d;
            if(tmp==0)break;
        }
    }
    return flow-tmp;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int u,v,f;
        scanf("%d%d%d",&u,&v,&f);
        add(u,v,f);
        add(v,u,0);
    }
    while(bfs())ans+=dinic(s,INT_MAX);
    printf("%lld",ans);
}  ```

by 血色黄昏 @ 2021-01-17 19:14:00

@zpl__hhd

#include <bits/stdc++.h>
using namespace std;
const int maxn=210,maxm=5010;
int n,m,s,t,cnt=1;//注意cnt=1！！！！！
long long ans;
int head[maxn],cur[maxn],dis[maxn];
struct edge
{
    int t,next;
    long long f;
}e[maxm<<1];
void add(int f,int t,long long w)
{
    e[++cnt].f=w;
    e[cnt].t=t;
    e[cnt].next=head[f];
    head[f]=cnt;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    cur[s]=head[s];
    queue<int> q;
    q.push(s);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].next)
        {
            int v=e[i].t;
            if(e[i].f&&dis[v]==-1)
            {
                dis[v]=dis[x]+1;
                cur[v]=head[v];
                q.push(v);
            }
        }
    }
    return dis[t]!=-1;
}
long long dinic(int x,long long flow)
{
    if(x==t)return flow;
    long long tmp=0;
    for(int i=cur[x];i;i=e[i].next)
    {
        cur[x]=i;
        int v=e[i].t;
        if(e[i].f&&dis[v]==dis[x]+1)
        {
            long long d=dinic(v,min(e[i].f,flow));
            if(d==0)dis[v]=INT_MAX;
            e[i].f-=d;
            e[i^1].f+=d;
            tmp+=d;
            flow -= d;
            if(flow==0)break;
        }
    }
    if(tmp == 0)dis[x] = 0;
    return tmp;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int u,v,f;
        scanf("%d%d%d",&u,&v,&f);
        add(u,v,f);
        add(v,u,0);
    }
    while(bfs())ans+=dinic(s,INT_MAX);
    printf("%lld",ans);
}

by 血色黄昏 @ 2021-01-17 19:15:33

@zpl__hhd 没搞懂您dinic里的tmp和flow到底都是起啥作用的...反正flow看做in，tmp看做out初始赋值为0然后如果tmp为0dis就设为0，最后return tmp

by 幻影星坚强 @ 2021-01-17 19:16:43

            long long d=dinic(v,min(e[i].f,flow));

后面应该是tmp

by zpl__hhd @ 2021-01-17 20:05:08

@幻影星坚强 谢谢DALAO指出蒟蒻错误

by zpl__hhd @ 2021-01-17 20:06:48

@血色黄昏 这是最大流的另一种做法，统计的是残量。谢谢DALAO，可能是个人写法不同的原因吧。

by 血色黄昏 @ 2021-01-17 20:09:20

@zpl__hhd 啊谢谢

by Kkfrqwfvqb @ 2021-01-17 20:19:09

我拿你代码试了一遍 直接AC了啊？？？