忘尘漪 @ 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了。。评测详情这就很迷。。。