Dinic T了5个点 求助

Herio @ 2020-06-30 18:08:07

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200+10,M=1e4+5,mod=1e9+7;
const ll inf=1e15;
#define mst(a) memset(a,0,sizeof a)
#define fmst(a) memset(a,-1,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int n,m,s,t,h[M],cur[M],cnt,dep[M];
struct node{
    int to,nt;
    ll w;
}e[M];
void add(int u,int v,ll w){
    e[cnt]={v,h[u],w};
    h[u]=cnt++;
}
bool bfs(){
    fmst(dep);
    queue<int>q;
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];~i;i=e[i].nt){
            int v=e[i].to;
            ll w=e[i].w;
            if(dep[v]==-1&&w)
                dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]!=-1;
}
ll dfs(int u,ll flow){
    if(u==t) return flow;
    ll delta=flow;
    for(int i=cur[u];~i;i=e[i].nt){
        cur[u]=e[i].nt;
        int v=e[i].to;
        ll w=e[i].w;
        if(dep[v]==dep[u]+1&&e[i].w>0){
            ll x=dfs(v,min(flow,1LL*e[i].w));
            e[i].w-=x,e[i^1].w+=x;
            delta-=x;
            if(!delta) break;
        }
    }
    return flow-delta;
}
ll dinic(){
    ll ans=0;
    while(bfs()){
        for(int i=1;i<=n;i++)
            cur[i]=h[i];
        ans+=dfs(s,inf);
    }
    return ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    fmst(h);
    for(int i=1;i<=m;i++){
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    printf("%lld\n",dinic());
    return 0;
}

by SmokedFish @ 2020-06-30 18:09:46

这题的数据不是出了名的duliu吗（

by Laser_Crystal @ 2020-06-30 18:23:56

@HeHao147989 这这这……怕是写了个假的Dinic吧……这题EK都能过的……

by Herio @ 2020-06-30 18:31:18

@Lattle_Car

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200+10,M=1e4+5,mod=1e9+7;
const ll inf=1e15;
#define mst(a) memset(a,0,sizeof a)
#define fmst(a) memset(a,-1,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int n,m,s,t,h[M],cur[M],cnt,dep[M];
struct node{
    int to,nt;
    ll w;
}e[M];
void add(int u,int v,ll w){
    e[cnt]={v,h[u],w};
    h[u]=cnt++;
}
bool bfs(){
    fmst(dep);
    queue<int>q;
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=h[u];~i;i=e[i].nt){
            int v=e[i].to;
            ll w=e[i].w;
            if(dep[v]==-1&&w>0)
                dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t]!=-1;
}
ll dfs(int u,ll flow){
    if(u==t) return flow;
    ll delta=flow;
    for(int i=cur[u];~i;i=e[i].nt){
        cur[u]=i;
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w>0){
            ll x=dfs(v,min(flow,e[i].w));
            e[i].w-=x,e[i^1].w+=x;
            delta-=x;
            if(!delta) break;
        }
    }
    return flow-delta;
}
ll dinic(){
    ll ans=0;
    while(bfs()){
        for(int i=1;i<=n;i++)
            cur[i]=h[i];
        ans+=dfs(s,inf);
    }
    return ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    fmst(h);
    for(int i=1;i<=m;i++){
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    printf("%lld\n",dinic());
    return 0;
}

改了一下,WA了三个点，应该是我写假了，但是不知道错误在哪。

by Laser_Crystal @ 2020-06-30 18:33:57

@HeHao147989 （我不会Dinic……我只会EK……别D我这个菜鸡……qwq……