EK求助，8-10号点WA

otislee601 @ 2022-01-26 16:32:09

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define ll long long
#define int long long
using namespace std;
const ll maxn = 1e4 + 100;
const ll inf = 0x7fffffff;
struct edge{ll v,w,rev;};
ll n,m,S,T,pos[maxn][maxn],minn[maxn],pre[maxn],ans;
vector <edge> G[maxn];
bool vis[maxn];
bool bfs()
{
    queue <ll> q;
    q.push(S);
    minn[S]= inf;
    vis[S] = 1;
    while(!q.empty())
    {
        ll tmp = q.front();
        q.pop();
        for(ll i = 0;i < G[tmp].size();++i)
        if(G[tmp][i].w>0)
        {
            if(vis[G[tmp][i].v]) continue;
            minn[G[tmp][i].v] = min(minn[tmp],G[tmp][i].w);
            pre[G[tmp][i].v] = tmp;
            q.push(G[tmp][i].v);
            vis[G[tmp][i].v] = 1;
            if(G[tmp][i].v==T) return 1;
        }
    }
    return 0;
}
ll update()
{
    ll x = T;
    while(x != S)
    {
        G[pre[x]][pos[pre[x]][x]].w -= minn[T];
        G[x][G[pre[x]][pos[pre[x]][x]].rev].w += minn[T];
        x = pre[x];
    }
    return minn[T];
}
ll ek(ll s,ll t)
{
    ll flow = 0;
    while(1)
    {
        memset(vis,0,sizeof(vis));
        bool f = bfs();
        if(f == 0) return flow;
        flow += update();
    }
}
main()
{
    cin >> n >> m >> S >> T;
    for(ll i = 1,u,v,w;i <= m;++i)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        if(!pos[u][v])
        {
            G[u].push_back((edge){v,w,G[v].size()});
            G[v].push_back((edge){u,0,G[u].size()-1});
            pos[u][v] = G[u].size() - 1;
        }
        else  G[u][pos[u][v]].w += w;
    }
    printf("%lld\n",ek(S,T));
    return 0;
}

by AzusagawaKaede @ 2022-01-26 19:06:08

你怎么学网络流了/jk

by AzusagawaKaede @ 2022-01-26 20:05:28

1. pos[u][v] = G[u].size() - 1;有误。当G[u].size() - 1的值为0时，对重边的判定if(!pos[u][v])会失效。建议将pos数组全初始化为-1，判定改为if(pos[u][v]==-1)。

2. pos[u][v] = G[u].size() - 1;还有误qwq。应将其反边v->u也存入pos，即添加一行代码pos[v][u] = G[v].size() - 1;。当然这个时候你就不需要rev了。

3. maxn应设为205,因为那些数组都是存的下标都是指结点。你设得太大会使pos[maxn][maxn]爆空间，在你谷下可能没事，但在NOILinux下会直接全MLE。

然后就可以AC了呢~

by AzusagawaKaede @ 2022-01-26 20:10:27

这是修改后的代码awa：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define ll long long
#define int long long
using namespace std;
const ll maxn = 205;//不算错误的错误3
const ll inf = 0x7fffffff;
struct edge{ll v,w,rev;};
ll n,m,S,T,pos[maxn][maxn],minn[maxn],pre[maxn],ans;
vector <edge> G[maxn];
bool vis[maxn];
bool bfs()
{
    queue <ll> q;
    q.push(S);
    minn[S]= inf;
    vis[S] = 1;
    while(!q.empty())
    {
        ll tmp = q.front();
        q.pop();
        for(ll i = 0;i < G[tmp].size();++i)
        if(G[tmp][i].w>0)
        {
            if(vis[G[tmp][i].v]) continue;
            minn[G[tmp][i].v] = min(minn[tmp],G[tmp][i].w);
            pre[G[tmp][i].v] = tmp;
            q.push(G[tmp][i].v);
            vis[G[tmp][i].v] = 1;
            if(G[tmp][i].v==T) return 1;
        }
    }
    return 0;
}
ll update()
{
    ll x = T;
    while(x != S)
    {
        G[pre[x]][pos[pre[x]][x]].w -= minn[T];
        G[x][G[pre[x]][pos[pre[x]][x]].rev].w += minn[T];
        x = pre[x];
    }
    return minn[T];
}
ll ek(ll s,ll t)
{
    ll flow = 0;
    while(1)
    {
        memset(vis,0,sizeof(vis));
        bool f = bfs();
        if(f == 0) return flow;
        flow += update();
    }
}
main()
{
    cin >> n >> m >> S >> T;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            pos[i][j] = -1;//错误1
    for(ll i = 1,u,v,w;i <= m;++i)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        if(pos[u][v] == -1)//错误1
        {
            G[u].push_back((edge){v,w,G[v].size()});
            G[v].push_back((edge){u,0,G[u].size()-1});
            pos[u][v] = G[u].size() - 1;
            pos[v][u] = G[v].size() - 1;//错误2
        }
        else  G[u][pos[u][v]].w += w;
    }
    printf("%lld\n",ek(S,T));
    return 0;
}

by otislee601 @ 2022-01-26 22:58:53

谢谢zzy大佬！
我的垃圾代码我自己都看不下去，您尽然有耐心一行行看玩，调出来
（话说luogu的数据太水，这都能73

by otislee601 @ 2022-01-26 23:01:23

话说dalao最近在学什么