为什么用简单的EK算法跑,最后居然是MLE,不是超时

P3376 【模板】网络最大流

残酷月光 @ 2019-08-07 09:24:13

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#define Max 10005
#define inf 0x3f3f3f3f
#define max(a,b) a>b?a:b;
#define min(a,b) a>b?b:a;

using namespace std;
queue<int> q;
int n,m,x,y,w,st,end;
int g[Max][Max]; //目前还剩的容量
int pre[Max];//保存增广路径
int flow[Max]; //源点到目前点的最大流量
int max_flow;//ans
void init()
{
    max_flow=0;
    memset(flow,0,sizeof(flow));
    memset(g,0,sizeof(g));
}
inline int bfs(int st,int end)
{
    while(q.size()) q.pop();
    for(int i=1;i<=n;i++) //点初始化
        pre[i]=-1;
    pre[st]=0;
    q.push(st);
    flow[st]=inf;
    int temp;
    while(q.size())
    {
        temp=q.front();
        q.pop();
        if(temp==end) break;//到汇点了
        for(int i=1;i<=n;i++)
        {
            if(g[temp][i]>0&&pre[i]==-1)
            {
                pre[i]=temp;
                flow[i]=min(flow[temp],g[temp][i]);  //维护最小值
                q.push(i);
            }
        }
    }
    if(pre[end]==-1)
        return -1;
    else
        return flow[end];
}
void EK(int st,int end)
{
    int increase=0;  //每次增加的流量
    int last;
    while((increase=bfs(st,end))!=-1)
    {
        int k=end;
        while(k!=st) //搜索已经找到的增广路劲
        {
            last=pre[k];
            g[last][k]-=increase; //正向减少
            g[k][last]+=increase; //反向增加
            k=last;
        }
        max_flow+=increase;
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&end);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        g[x][y]+=w;
    }
    EK(st,end);
    printf("%d\n",max_flow);
    return 0;
}

奇怪的是还有70分。难道是队列炸了??还是没过.....


by 残酷月光 @ 2019-08-07 09:26:00

而且炸的数据,本地能跑出来。。。。


by installb @ 2019-08-07 09:28:04

int g[Max][Max];

明显开不下这么大啊
这题不能邻接矩阵存图


by 残酷月光 @ 2019-08-07 09:31:50

@installb 但是还有70分,这让我很怀疑。,我本来觉得应该会超时,毕竟每次遍历全部,但是居然有70分,有点奇怪。。


by 童年如作业 @ 2019-08-07 09:43:47

@残酷月光 这我试过


by 童年如作业 @ 2019-08-07 09:46:03

还有这是模板,估计是为了大家的代码无论写多丑、不卡常,思想对都能跑出AC,数据肯定不会特别卡(不然你让Dinic怎么活)


by 残酷月光 @ 2019-08-07 09:52:35

@童年如作业 Dinic一般不是比EK更快嘛?一个O(VE^2) 一个O(V^2E) 显然边大于点


by 童年如作业 @ 2019-08-07 10:01:21

@残酷月光 我知道啊,我说的是模板可能并不在时间上卡算法


by 童年如作业 @ 2019-08-07 10:02:03

(当然你打超级无敌大暴力就当我没说)


by Magallan_forever @ 2019-09-28 16:58:30

@童年如作业 【模板】快速排序


|