90分RE,谁能帮看看

P3376 【模板】网络最大流

kIG7Z8oP @ 2019-02-10 19:30:24

//第二个点R了
//dinic算法
//bfs分层并判断是否连通
//d[]表示深度,c容量f流量,rev反边 
//cur:当前弧优化 
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=10010;
struct Edge
{
    int from,to,cap,flow,rev;
    Edge(){}
    Edge(int _from,int _to,int _cap,int _flow,int _rev): from(_from),to(_to),cap(_cap),flow(_flow),rev(_rev){}; 
};
vector<Edge> g[MAXN];
int cur[MAXN],s,t;
void insert(int u,int v,int c)//u->v,容量c 
{
    g[u].push_back(Edge(u,v,c,0,g[v].size()));
    g[v].push_back(Edge(v,u,0,0,g[u].size()-1));
}
int d[MAXN];
struct queue
{
    int val[MAXN],head,tail;
    void push(int k){val[tail]=k;tail++;}
    int top(){return val[head];}
    void pop(){head++;}
    bool empty(){return head==tail;}
    queue(){}
};
queue q;
int bfs()//找层,并判断是否是联通的 
{
    memset(d,0,sizeof(d));
    q.push(s);
    d[s]=1;
    while(!q.empty())
    {
        int now=q.top();
        q.pop();
        for(int i=0;i<g[now].size();i++)
        {
            Edge e=g[now][i];
            if(!d[e.to]&&e.cap>e.flow) d[e.to]=d[now]+1,q.push(e.to);
        }
    }
    return d[t];
}
int dfs(int now,int a)//available
{
    if(now==t||!a) return a;
    int flow=0;
    for(int &i=cur[now];i<g[now].size();i++)//记住这段话 
    {
        Edge &e=g[now][i];
        if(d[e.to]==d[now]+1&&e.cap>e.flow)
        {
            int f=dfs(e.to,min(a,e.cap-e.flow));
            a-=f,flow+=f,e.flow+=f,g[e.to][e.rev].flow-=f;
        } 
        if(!a) break;
    }
    if(a) d[now]=-1;
    return flow;
}
int n,m;
int main()
{
    int fr,too,c;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&fr,&too,&c);
        insert(fr,too,c);
    }
    int res=0;
    while(bfs())
    {
        memset(cur,0,sizeof(cur));
        res+=dfs(s,2147483647);
    }
    printf("%d",res);
}

by Resux @ 2019-02-10 20:19:41

这是哪一题?


by Catalan1906 @ 2019-02-10 20:42:37

@kIG7Z8oP

不知道诶……你把queue改成手写的试试,如果实在不行开long long?(不过这道题似乎不用long long)


by Catalan1906 @ 2019-02-10 20:46:50

@kIG7Z8oP 如果还是找不到错就把vector改成前向星吧……


by Catalan1906 @ 2019-02-10 20:47:22

@kIG7Z8oP 刚刚看错了……你的queue似乎就是手写的,把它改成stl试试


by kIG7Z8oP @ 2019-02-10 21:22:26

@Neptune_Disaster QAQ


by Catalan1906 @ 2019-02-10 21:23:57

@kIG7Z8oP 我没写过当前弧优化……你用正常的Dinic或许能过呢qwq


by kIG7Z8oP @ 2019-02-11 08:07:49

@Neptune_Disaster 锅出在bfs上


by revolIA @ 2019-03-04 17:33:22

我来告诉你,很简单,你把maxn改成1e5就可以了,估计是出题人数据范围没写好,我也re过


|