死循环了,我看了不下30遍正确代码了555

P3376 【模板】网络最大流

FF_pigeon @ 2023-07-11 19:15:47

#include<bits/stdc++.h>
#define ll long long 
#define INF 0x3f3f3f3f
using namespace std;
int n, m, s, t;
const int N = 205;
const int M = 5e3+100;
struct Edge
{
    int to, nxt;
    ll flow;
}e[M*2];
int head[N], dis[N], cur[N], ecnt = 1;
void addedge( int u , int v , int fl )
{
    e[++ecnt]=(Edge){v,head[u],fl};head[u] = ecnt;
    e[++ecnt]=(Edge){u,head[v],0};head[v] = ecnt;
}
bool BFS()
{

    memset(dis,0x3f,sizeof(dis));
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while( !q.empty() )
    {
        int u = q.front();
        q.pop();
        for( int i = head[u] ; i ; i = e[i].nxt )
        {
            if( e[i].flow != 0 && dis[e[i].to] == INF)
            {   
                dis[e[i].to] = dis[u]+1;
                q.push(e[i].to); 
            }
        }
    }
    return dis[t] != INF;
}
ll DFS( int u , ll a )
{
    if( u == t || a == 0 ) return a;
    ll ret = 0;
    for( int &i = cur[i] ; i ; i = e[i].nxt )
    {
        if( e[i].flow == 0 || dis[e[i].to] != dis[u]+1 )continue;
        int f = DFS(e[i].to,min(a,e[i].flow));
        if( f )
        {

            ret += f;
            e[i].flow -= f;
            e[i^1].flow += f;
            a -= f;
            if( a == 0 ) return ret;
        }
    }
}
ll Dinic( int S1 , int T1 )
{

    s = S1;
    t = T1;
    ll ret = 0;
    while( BFS() )
    {
        memcpy(cur,head,sizeof(cur));
        ret += DFS(s,INF);
    }
    return ret;
}
int main()
{
    memset(head,0,sizeof(head));
    cin >> n >> m >> s >> t;
    int a, b, c;
    for( int i = 1 ; i <= m ; ++i )
    {
        cin >> a >> b >> c;
        addedge(a,b,c);
    }
    ll ans = Dinic(s,t);
    cout << ans << endl;

    return 0;
}

不想多言


by wrkwrkwrk @ 2023-07-11 19:25:23

for( int &i = cur[i] ; i ; i = e[i].nxt )//cur[i]的i哪里来的

应写成

for( int &i = cur[u] ; i ; i = e[i].nxt )

在DFS函数末尾加上return ret;

另外,建议在本地编译时加-Wall


by Aleph_Drawer @ 2023-07-11 19:27:46

两个都会报错捏()


by FF_pigeon @ 2023-07-11 19:56:26

谢谢大佬~~ (滑跪) ~~ 已AC


|