有愿意调试EK的吗？

yummy @ 2020-03-21 14:14:14

by yummy @ 2020-03-21 14:15:04

60分，2,5,6,10WA。

#include<bits/stdc++.h>
#define rint register int
using namespace std;
inline int read()
{
    int tot=0;
    char c=getchar();
    while(c<'0' || c>'9')
        c=getchar();
    while(c>='0' && c<='9')
    {
        tot=tot*10+c-'0';
        c=getchar();
    }
    return tot;
}//以上部分可以忽略
struct edge
{
    int to,flow;
};
int n,m,s,t,u,v,w,fl[10005],pre[10005],pred[10005];
bool vis[10005];
vector<edge> g[10005];//残余网络
queue<int> qwq;//bfs的队列
int max_flow()//求一条增广路并返回
{
    qwq.push(s);
    memset(vis,0,sizeof(vis));
    memset(fl,0,sizeof(fl));
    fl[s]=0x3f3f3f3f;
    vis[s]=1;
    while(!qwq.empty())
    {
        int qf=qwq.front();//本轮bfs的结点
        for(int i=0;i<g[qf].size();i++)
        {
            if(g[qf][i].flow==0)//如果是空边则删除
            {
                swap(g[qf][i],*g[qf].rbegin());
                g[qf].pop_back();
            }
            else if(!vis[g[qf][i].to])//由于只要找一条，所以哪怕这一条流量更大也不管（
            {
                pre[g[qf][i].to]=qf;//g[qf][i].to的最短路来自qf
                pred[g[qf][i].to]=i;//来自qf的第i条边
                vis[g[qf][i].to]=1;
                fl[g[qf][i].to]=min(fl[qf],g[qf][i].flow);
                qwq.push(g[qf][i].to);
            }
        }
        qwq.pop();
    }
    int tmp=t;
    while(tmp!=s)//扣除这条边的费用
    {
        g[pre[tmp]][pred[tmp]].flow-=fl[t];
        g[tmp].push_back((edge){pre[tmp],fl[t]});//添加反向边
        tmp=pre[tmp];
    }
    return fl[t];
}
int main()
{
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        u=read();v=read();w=read();
        g[u].push_back((edge){v,w});
    }
    long long flow=0;
    int nfl;
    do
    {
        nfl=max_flow();//NowFLow表示当前的增广路
        flow+=nfl;//总流量加上当前流量
    }while(nfl);//重复直到没有增广路
    printf("%lld",flow);
    return 0;
}

by xhQYm @ 2020-03-21 14:15:15

orz不会网络流

by BFqwq @ 2020-03-21 14:29:14

不会 EK。。。

by XeCtera @ 2020-03-21 14:30:14

写法神奇（

by _Zhumingrui @ 2020-03-21 14:34:12

我太菜了，不会EK

by tidongCrazy @ 2020-03-21 14:34:28

写法神奇（

by andyli @ 2020-03-21 14:43:06

写法神奇（

by 45dino @ 2020-03-21 14:43:50

我太菜了，只会Dinic

by yummy @ 2020-03-21 14:47:05

@andyli 所以思路有问题吗

by andyli @ 2020-03-21 14:49:23

@yummy 删边时会不会导致pred数组存的位置改变？