PotatoServer @ 2019-02-01 15:11:18
第二个点WA了...最后两个点RE了...感觉显然哪里除了沙雕错误但就是找不出来
#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int inf = 1e9;
int n,m,s,t;
queue<int>q;
struct edge {
int next = -1;
int to;
int dis;
};
edge road[100005];
int head[10005];
int roadindex = 0;
int deep[10005];
void addroad(int u, int v, int w, int zero){
road[roadindex].dis = w;
if (zero)road[roadindex].dis = 0;
road[roadindex].to = v;
road[roadindex].next = head[u];
head[u] = roadindex;
roadindex++;
}
void clear(){
memset (deep, -1, sizeof(deep));
}
bool bfs(){
clear();
while (!q.empty())q.pop();
deep[s] = 1;
q.push(s);
while (!q.empty()){
int inow = q.front();
for (int i = head[inow]; i != -1; i = road[i].next){
int nxt = road[i].to;
if (road[i].dis <= 0)continue;
if (deep[nxt] <= 0){
deep[nxt] = deep[inow] + 1;
q.push(nxt);
}else if (deep[nxt] > deep[inow] + 1){
deep[nxt] = deep[inow] + 1;
q.push(nxt);
}
}
q.pop();
}
if (deep[t] > 0){
return true;
}else{
return false;
}
}
int dfs (int now, int limit){
if (now == t || limit == 0)return limit;
int flow = 0;
for (int i = head[now]; i != -1; i = road[i].next){
int nxt = road[i].to;
if (road[i].dis > 0 && deep[nxt] == deep[now] + 1){
flow = min (dfs (nxt, min (limit, road[i].dis)), limit);
if (flow > 0){
road[i].dis -= flow;
road[i^1].dis += flow;
break;
}
}else{
continue;
}
}
return flow;
}
int main (){
scanf ("%d %d %d %d", &n, &m, &s, &t);
memset (head, -1, sizeof(head));
clear();
for (int i = 0; i < m; i++){
int u=0,v=0,w=0;
scanf ("%d %d %d", &u, &v, &w);
addroad(u,v,w,0);
addroad(v,u,w,1);
}
int ans = 0;
while (bfs()){
while (true){
int emm = dfs (s, inf);
if (emm == 0)break;
ans += emm;
}
}
printf ("%d", ans);
return 0;
}
by xiaolou @ 2019-02-01 15:13:01
@PotatoServer 网络流正反两次建边,pool开200000
by PotatoServer @ 2019-02-01 22:23:59
@xiaolou !!!成了 谢谢