本题题目的数据似乎有点弱

P3376 【模板】网络最大流

忘尘漪 @ 2019-06-09 19:35:34

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
const int inf = 1e9;
inline int read(){
    int w=1,q=0;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return w*q;
}

struct edge{
    int from,to,w;
    edge(int u, int v, int _w):from(u),to(v),w(_w){}
};
vector<edge> edges;
vector<int> g[maxn];
int dep[maxn],n,m,s,t,cur[maxn];

void addedge(int u, int v, int w){
    int cnt;
    edges.push_back(edge(u,v,w)); 
    cnt = edges.size()-1;
    g[u].push_back(cnt);
    edges.push_back(edge(v,u,0));
    cnt = edges.size()-1;
    g[u].push_back(cnt);
}

bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s] = 1;
    int u,v;
    while(!q.empty()){
        u = q.front();
        q.pop();
        for(int i = 0; i < g[u].size(); i++){
            edge &e = edges[g[u][i]];
            if(e.w>0 && dep[e.to]==0){
                dep[e.to] = dep[u] + 1;
                q.push(e.to);
            }
        }
    }
    if(!dep[t]) return 0;
    return 1;
}
int cnt = 0;
int dfs(int u, int dist){
    if(u==t)
        return dist;
    for(int &i = cur[u]; i < g[u].size(); i++){
        edge &e = edges[g[u][i]];
        if(dep[e.to] == dep[u]+1 && e.w != 0){
            int ret = dfs(e.to,min(dist,e.w));
            if(ret > 0){
                e.w -= ret;
                edges[g[u][i]^1].w += ret;
                return ret;
            }
        }
    }
    return 0;
}

int dicnic(){
    int ret = 0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        ret += dfs(s,inf);
    }
    return ret;
}

int main(){
    n = read(); m = read(); s = read(); t = read();
    int u,v,w;
    for(int i = 1; i <= m; i++){
        u = read(); v = read(); w = read();
        addedge(u,v,w); 
    }
    cout << dicnic();
    return 0;
} 

如上的代码在addedge函数中建立反向边时,应该g[v].push_back,开始做的时候写错了,写成g[u]了,居然还能ac了。。评测详情这就很迷。。。


|