Dinic 63分求助

P3376 【模板】网络最大流

王奕霏 @ 2020-09-19 15:31:14

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;
int n, m, sorce, target, cnt;
int heads[10010], level[10010];
struct Node{
    int from;
    int to;
    int capacity;
    int next;
};
Node edges[100010];

void add(int f, int t, int c){
    edges[cnt].from=f;
    edges[cnt].to=t;
    edges[cnt].capacity=c;
    edges[cnt].next=heads[f];
    heads[f]=cnt;
    swap(f, t); cnt++;
    edges[cnt].from=f;
    edges[cnt].to=t;
    edges[cnt].capacity=0;
    edges[cnt].next=heads[f];
    heads[f]=cnt; cnt++;
    return;
}

bool bfs(){
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(sorce);
    level[sorce]=0;
    while(!q.empty()){
        int top=q.front(); q.pop();
//      cout << top << endl;
        if(top==target) return true;
        for(int i=heads[top];i!=-1;i=edges[i].next){
            int t=edges[i].to;
            int c=edges[i].capacity;
//          printf("edges[%d]: from=%d, to=%d, capacity=%d, next=%d\n", i, edges[i].from, t, c, edges[i].next);
            if(level[t]==-1 && c>0){
                level[t]=level[top]+1;
                q.push(t);
            }
        }
    }
    return false;
}

int dfs(int u, int mx){
//  cout << u << endl;
    if(u==target || mx<=0) return mx;
    int sum=0;
    for(int i=heads[u];i!=-1;i=edges[i].next){
        int t=edges[i].to;
        int c=edges[i].capacity;
//      cout << t << endl;
        if(level[t]==level[u]+1 && c>0){
            int ans=dfs(t, min(mx-sum, c));
            sum+=ans;
            edges[i].capacity-=ans;
            edges[i^1].capacity+=ans;
            if(sum==mx) return mx;
        }
    }
    return sum;
}

int dinic(){
    int ans=0;
    while(bfs()){
//      printf("1 ");
        ans+=dfs(sorce, 0x3f3f3f3f);
//      printf("\n\n\n\n\n\n");
    }
//  printf("\n");
    return ans;
}

int main(){
    scanf("%d%d%d%d", &n, &m, &sorce, &target);
    memset(heads, -1, sizeof(heads));
    for(int i=0;i<m;i++){
        int f, t, c;
        scanf("%d%d%d", &f, &t, &c);
        add(f, t, c);
    }
    printf("%d\n", dinic());
    return 0;
}

by metaphysis @ 2020-09-19 18:13:09

@王奕霏

读题时对数据范围要特别注意:0≤w<2 ^{31}。 Hack数据:

4 4 1 4
1 2 2147483647
1 3 2147483647
2 4 2147483647
3 4 2147483647

您的输出:

-2

正确输出:

4294967294

by metaphysis @ 2020-09-19 18:15:47

@王奕霏

您先把这个问题修正先看能不能AC,如果有问题的话,我再帮您看看。


by 王奕霏 @ 2020-10-09 17:10:50

@metaphysis 好的好的 非常感谢


|