Dinic只有20pts求救

P3376 【模板】网络最大流

Vsinger_洛天依 @ 2024-09-04 21:16:02

感觉写的挺对的,但是只有20分

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define int long long
#define ull unsigned long long
#define re register
#define for_(a,b,P) for(int a=b;a<=P;a++)
#define _for(a,b,P) for(int a=b;a>=P;a--)
#define firein(a) freopen(a".in","r",stdin)
#define fireout(a) freopen(a".out","W",stdout)
#define fire(a) (firein(a),fireout(a))
#define lc(q) (q<<1)
#define rc(q) (q<<1|1)
#define mid(l,r) ((l+r)>>1)

using namespace std;

namespace IO{
    inline int read(){
        char ch=getchar();
        int s=0,f=1;
        while(ch<'0'||'9'<ch) {
            if(ch == '-'){
                f = -1;
            }
            ch = getchar();
        }
        while('0'<ch&&ch<'9'){
            s = s*10 + ch - '0';
            ch = getchar();
        }
        return s * f;
    }

    inline void write(int x){
        if(x < 0){
            putchar('-');
            x *= -1;
        }
        write(x/10);
        putchar(x%10 + '0'); 
    }

    inline void print(int x,char s){
        write(x);
        putchar(s);
    }

    inline double rnd(){
        char P = getchar();
        int f = 1,s = 0,x = 0;
        double t = 0;

        while((P<'0'||P>'9')&&P!='.'){
            if(P == '-')
                f *= -1;
            P = getchar();
        }
        while(P>='0'&&P<='9'&&P!='.'){
            x = x*10 + (P^48);
            P = getchar();
        }

        if(P=='.'){
            P=getchar();
        }
        else{ 
            return x*f;
        }

        while(P>='0'&&P<='9'){
            s+=1;
            t=t*10+(P^48);
            P=getchar();
        }
        while(s--){
            t/=10.0;
            x=(x+t)*f;
        }

        return x;
    }
}
using namespace IO;

const int N = 1000005;
const int M = 10000005;
const ll INF=0x66ccff0712ll;
const ll inf=LLONG_MAX;

int Head[N],ver[N],Edge[N],nxt[N],d[N];
int now[N],tot,n,m,s,t,maxflow,flow;

inline void Add(int x,int y,int z){
    ver[++tot] = y;
    Edge[tot] = z;
    nxt[tot] = Head[x];
    Head[x] = tot; 
}

queue<int> q;
inline bool BFS(){
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s);
    d[s] = 1; now[s] = Head[s];
    while(q.size()){
        int x = q.front(); q.pop();
        for(int i=Head[x] ; i ; i=nxt[i]){
            if(Edge[i] && !d[ver[i]]){
                q.push(ver[i]);
                now[ver[i]] = Head[ver[i]];
                d[ver[i]] = d[x] + 1;
                if(ver[i] == t) return 1;
            }
        }
    }
    return 0;
}

inline int Dinic(int x,int f){
    if(x==t) return f;
    int rest = f;
    for(int i = now[x];i && rest;i = nxt[i]){
        now [x] = i;
        if(Edge[i] && d[ver[i]] == d[x] + 1){
            int k = Dinic(ver[i],min(rest,Edge[i]));
            if(!k) d[ver[i]] = 0;
            Edge[i] -= k;
            Edge[i^1] += k;
            rest -= k;
        }
    }
    return f - rest;
}

inline void In(){
    cin >> n >> m >> s >> t;
    tot = 1;
    for_(i,1,m){
        int x,y,z;
        cin >> x >> y >> z;
        Add(x,y,z);
        Add(y,x,z);
    }
    while(BFS())
        while(flow=Dinic(s,inf))
            maxflow += flow;
    cout << maxflow << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    In();
}

by Vsinger_洛天依 @ 2024-09-04 21:16:47

input

10 25 3 1
9 3 80
5 10 62
4 2 13
7 2 20
3 10 90
6 10 53
2 3 11
6 3 45
9 5 37
10 9 93
7 8 28
4 5 28
1 2 52
4 5 54
1 2 62
7 4 64
4 3 40
7 3 39
8 2 72
7 5 5
3 6 88
3 2 56
9 2 72
2 1 81
6 7 84
right output

81

by LuoMuxiaoxiao @ 2024-09-04 21:25:11

咋还在写题,不是军训?


by _空白_ @ 2024-09-25 19:01:31

@Vsinger_洛天依 反边初始权值应该是0吧


|