Dinic算法vector样例过不了求调

P3376 【模板】网络最大流

qip101 @ 2022-12-31 12:30:44

#include <bits/stdc++.h> 
#define MAXN 100100
#define MAXM 2023
#define INF 2147483647
using namespace std;
long long n,m,s,t,ans;
long long dis[MAXM];
struct edge{
    int v,w;
};
vector <edge> G[MAXN];
inline void add_edge(int u,int v,int w)
{
    G[u].push_back((edge){v,w});
    G[v].push_back((edge){u,0});
}
inline bool BFS()
{
    memset(dis,INF,sizeof(dis));
    queue <int> q;
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<G[x].size();i++)
        {
            int to=G[x][i].v;
            if(G[x][i].w>0 && dis[to]==INF)
            {
                q.push(to);
                dis[to]=dis[x]+1;
                if(to==t)
                    return true;
            }
        }
    }
    return false;
}
int DFS(int x,int sum)
{
    if(x==t) 
        return sum;
    long long k,res=0;
    for(int i=0;i<G[x].size();i++)
    {
        int to=G[x][i].v;
        if(G[x][i].w>0 && dis[to]==dis[x]+1)
        {
            k=DFS(to,min(sum,G[x][i].w));
            if(k==0)
                dis[to]=INF;
            G[x][i].w-=k;
            G[x][i].w+=k;
            res+=k;
            sum-=k;
        }
    }
    return res;
}
void Dinic() 
{
    while(BFS()==true)
        ans+=DFS(s,INF);
}
int main()
{
    //freopen("Dinic.in","r",stdin);
    //freopen("Dinic.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> s >> t;
    for(int i=1;i<=m;i++) 
    {
        int u,v,w;
        cin >> u >> v >> w;
        add_edge(u,v,w);
    }
    Dinic();
    cout << ans << endl;
    return 0;
}

by 方123456 @ 2022-12-31 12:49:59

@死在水中的鱼 网络流的反向边和正向边咋一样呀 /fad

            if(k==0)
                dis[to]=INF;
            G[x][i].w-=k;
            G[x][i].w+=k;
            res+=k;
            sum-=k;

这里的 G[x][i].w 真的有实质改变么?


by char_cha_ch @ 2022-12-31 12:52:23

@死在水中的鱼 宁哪来的反边啊。要不邻接矩阵,要不就前向星。


by qip101 @ 2022-12-31 12:56:36

@方123456 应该怎么写哦?


by liangbowen @ 2022-12-31 13:46:24

@死在水中的鱼 应该是

G[x][i].w-=k;
G[反边].w+=k;

链式前向星里,反边就是 i ^ 1,vector就很难存。

可以再额外开一个数组,记录每条边的反边。不过还是 链前 方便(


by qip101 @ 2023-01-01 12:19:40

@liangbowen 反边应该就是G[i][x]?我改了以后还是输出0


by ssilrrr @ 2023-01-04 12:58:00

vector可以存边的指针。

而且,可以用map,但是带log。


|