玄学全RE

P3376 【模板】网络最大流

Union_of_Britain @ 2021-03-07 22:35:35

第一个点在luoguIDE上都没问题,在这里就RE。。。

都是C++17

照着训练指南打的


#include<bits/stdc++.h>
using namespace std;//Dinic求最大流
struct Edge
{
    int from,to,cap,flow;//cap容量,flow流量 
};
const int maxn=205;
const int INF=2<<29;
struct Dinic
{
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn]; 
    int d[maxn];//层次相关 
    int cur[maxn];
    void AddEdge(int from,int to,int cap)
    {
        edges.push_back((Edge){from,to,cap,0});
        edges.push_back((Edge){from,to,0,0});//残量
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1); 
    }
    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int> Q;
        Q.push(s);//源点
        d[s]=0; 
        vis[s]=1;
        while(!Q.empty())
        {
            int x=Q.front();
            //cout<<x<<endl;
            Q.pop();
            for(int i=0;i<G[x].size();i++)
            {
                Edge& e=edges[G[x][i]];
                //cout<<e.to<<endl;
                if(!vis[e.to]&&e.cap>e.flow)
                {
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];//可以被访问到 
    }
    int DFS(int x,int a)
    {
        if(x==t||a==0)return a;
        int flow=0,f;
        for(int& i=cur[x];i<G[x].size();i++)//当前弧优化
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)break;  
            }   
        }
        return flow; 
    }
    int Maxflow(int s,int t)
    {
        this->s=s;
        this->t=t;
        int flow=0;
        while(BFS())
        {
            //cout<<"BFS"<<endl;
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,INF);
        }
        printf("%d",flow);
    }
}; 
Dinic solve;
int main()
{
    cin>>solve.n>>solve.m>>solve.s>>solve.t;
    int rm=solve.m;
    for(int i=1;i<=rm;i++)
    {
        int x,y,l;
        cin>>x>>y>>l;
        solve.AddEdge(x,y,l);
    }
    //cout<<"Maxflow"<<endl;
    solve.Maxflow(solve.s,solve.t);
    return 0;
} ```

by Masna_Kimoyo @ 2021-03-07 23:47:15

名字危(居然和我是一类人


by 幻影星坚强 @ 2021-03-08 11:28:54

int函数没返回值,老生常谈了


by Union_of_Britain @ 2021-03-11 21:59:55

@幻影星坚强 过了,谢谢


|