EK 68分求调 玄关
查看原帖
EK 68分求调 玄关
930119
_Sonnet楼主2025/2/7 07:58

找增广路应该是没问题的,可能是流量算错了,但本蒟蒻找不出来TT

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 550000;
const int INF = 2005020600;
int n , m , s , t;
bool flag[3000][3000] , vis[N];
int head[N] , to[N] , ne[N] , id = 1;
int pre[N];
long long ans , dis[N] , w[N];
void add(int x , int y , long long z)
{
    to[++ id] = y;
    ne[id] = head[x];
    head[x] = id;
    w[id] = z;
    to[++ id] = x;
    ne[id] = head[y];
    head[y] = id;
}
int bfs()
{
    for(int i = 1 ; i <= n ; i ++)
    {
        vis[i] = 0;
    }
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    dis[s] = INF;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = head[x] ; i ; i = ne[i])
        {
            if(w[i] == 0)
                continue;
            int v = to[i];
            if(vis[v] == 1)
                continue;
            dis[v] = min(dis[x] , w[i]);
            //cout << v << ' ' << dis[v] << endl;
            pre[v] = i;
            q.push(v);
            vis[v] = 1;
            if(v == t)
                return 1;
        }
    }
    return 0;
}
void update()
{
    int x = t;
    while(x != s)
    {
        int v = pre[x];
        w[v] -= dis[t];
        w[v ^ 1] += dis[t];
        x = to[v ^ 1];
    }
    //cout << dis[t] << endl;
    /*
    15
    38
    19
    */
    ans += dis[t];
}
signed main()
{
    scanf("%lld%lld%lld%lld" , &n , &m , &s , &t);
    for(int i = 1 ; i <= m ; i ++)
    {
        int u , v ;
        long long W;
        scanf("%lld%lld%lld" , &u , &v , &W);
        if(flag[u][v] == 0)
        {
            add(u , v , W);
            //add(v , u , W);
            flag[u][v] = id;
        }
        else
        {
            w[flag[u][v] - 1] += W;
        }
    }
    //int ttt = 0;
    while(bfs())
    {
        update();
        //ttt++;
    }
    //cout << ttt << endl;
    printf("%lld" , ans);
    return 0;
}

2025/2/7 07:58
加载中...