题目描述
这是一道模板题。
n n n 个点,m m m 条边,每条边 e e e 有一个流量下界 lower(e) \text{lower}(e) lower(e) 和流量上界 upper(e) \text{upper}(e) upper(e),给定源点 s s s 与汇点 t t t,求源点到汇点的最大流。
输入格式
第一行两个正整数 n n n、m m m、s s s、t t t。
之后的 m m m 行,每行四个整数 s s s、t t t、lower \text{lower} lower、upper \text{upper} upper。
输出格式
如果无解,输出一行 please go home to sleep。
否则输出最大流。
样例
样例输入
10 15 9 10
9 1 17 18
9 2 12 13
9 3 11 12
1 5 3 4
1 6 6 7
1 7 7 8
2 5 9 10
2 6 2 3
2 7 0 1
3 5 3 4
3 6 1 2
3 7 6 7
5 10 16 17
6 10 10 11
7 10 14 15
样例输出
43
数据范围与提示
1≤n≤202,1≤m≤9999
代码示例 :
using namespace std; #define ll long long const int maxn = 1e5+5; const int mod = 1e9+7; const double eps = 1e-9; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; int n, m, s, t; struct node { int to, next, flow; }e[maxn]; int head[maxn]; int cnt = 0; void addedge(int u, int v, int w){ e[cnt].to = v, e[cnt].next = head[u], e[cnt].flow = w, head[u] = cnt++; e[cnt].to = u, e[cnt].next = head[v], e[cnt].flow = 0, head[v] = cnt++; } int dep[300]; int que[maxn]; bool bfs(int s, int t){ memset(dep, 0, sizeof(dep)); int head1 = 0, tail = 1; dep[s] = 1; que[0] = s; while(head1 < tail){ int v = que[head1++]; for(int i = head[v]; i != -1; i = e[i].next){ int to = e[i].to; if (e[i].flow && !dep[to]){ dep[to] = dep[v]+1; que[tail++] = to; } } } return dep[t]; } int aim; int dfs(int u, int f1){ if (u == aim || f1 == 0) return f1; int f = 0; for(int i = head[u]; i != -1; i = e[i].next){ int to = e[i].to; if (e[i].flow && dep[to] == dep[u]+1){ int x = dfs(to, min(f1, e[i].flow)); e[i].flow -= x, e[i^1].flow += x; f1 -= x, f += x; if (f1 == 0) return f; } } if (!f) dep[u] = -2; return f; } int dinic(int s, int t){ int res = 0; aim = t; while(bfs(s, t)){ //printf("++++\n"); res += dfs(s, inf); } return res; } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int a, b, c, d; int ss = 0, tt = n+1; memset(head, -1, sizeof(head)); cin >> n >> m >> s >> t; addedge(t, s, inf); int sum = 0; for(int i = 1; i <= m; i++){ scanf("%d%d%d%d", &a, &b, &c, &d); addedge(a, b, d-c); addedge(a, tt, c); addedge(ss, b, c); sum += c; } int flow = dinic(ss, tt); int ans = e[1].flow; //printf("ans = %d %d %d\n", ans, sum, e[1].flow); if (flow != sum) { printf("please go home to sleep\n"); return 0; } e[0].flow = 0, e[1].flow = 0; ans += dinic(s, t); printf("%d\n", ans); return 0; }