整理的算法模板合集： ACM模板
目录
无源汇上下界可行流有源汇上下界最大流有源汇上下界最小流
无源汇上下界可行流
#include <bits/stdc++.h>
using namespace std
;
const int oo
= (1LL << 31) - 1;
const int LEN
= 1e5 + 5;
struct node
{
int x
, y
, l
, r
;
} a
[LEN
];
namespace ISAP
{
int flow
, tot
, n
, m
, src
, tar
, qh
, qt
, cnt
, ans
;
struct edge
{
int vet
, next
, len
;
} E
[LEN
* 2];
int dis
[LEN
], gap
[LEN
], head
[LEN
], cur
[LEN
], q
[LEN
], vis
[LEN
], IN
[LEN
];
void add(int u
, int v
, int c
) {
E
[++tot
] = (edge
){v
, head
[u
], c
};
head
[u
] = tot
;
}
void join(int u
, int v
, int c
) {
add(u
, v
, c
);
add(v
, u
, 0);
}
void bfs(int s
) {
qh
= qt
= 0;
q
[++qt
] = s
;
dis
[s
] = 0;
vis
[s
] = 1;
while (qh
< qt
) {
int u
= q
[++qh
];
gap
[dis
[u
]]++;
for (int e
= head
[u
]; e
!= -1; e
= E
[e
].next
) {
int v
= E
[e
].vet
;
if (E
[e
^ 1].len
&& !vis
[v
]) {
dis
[v
] = dis
[u
] + 1;
vis
[v
] = 1;
q
[++qt
] = v
;
}
}
}
}
int isap(int u
, int aug
) {
if (u
== tar
) return aug
;
int flow
= 0;
for (int e
= head
[u
]; e
!= -1; e
= E
[e
].next
) {
int v
= E
[e
].vet
;
if (E
[e
].len
&& dis
[v
] == dis
[u
] - 1) {
int tmp
= isap(v
, min(aug
- flow
, E
[e
].len
));
E
[e
].len
-= tmp
;
E
[e
^ 1].len
+= tmp
;
flow
+= tmp
;
head
[u
] = e
;
if (flow
== aug
|| dis
[src
] == cnt
) return flow
;
}
}
if (!--gap
[dis
[u
]++]) dis
[src
] = cnt
;
++gap
[dis
[u
]];
head
[u
] = cur
[u
];
return flow
;
}
void init() {
tot
= -1, gap
[0] = 0;
for (int i
= 1; i
<= cnt
; i
++) {
dis
[i
] = gap
[i
] = vis
[i
] = IN
[i
] = 0;
head
[i
] = -1;
}
}
int maxflow(int s
, int t
) {
src
= s
, tar
= t
;
int res
= 0;
for (int i
= 1; i
<= cnt
; i
++) cur
[i
] = head
[i
];
bfs(tar
);
while (dis
[src
] < cnt
) res
+= isap(src
, oo
);
return res
;
}
}
using namespace ISAP
;
int main() {
scanf("%d %d", &n
, &m
);
cnt
= n
;
src
= ++cnt
, tar
= ++cnt
;
init();
for (int i
= 1; i
<= m
; i
++) {
int x
, y
, l
, r
;
scanf("%d %d %d %d", &x
, &y
, &l
, &r
);
a
[i
] = (node
){x
, y
, l
, r
};
join(x
, y
, r
- l
);
IN
[y
] += l
, IN
[x
] -= l
;
}
for (int i
= 1; i
<= n
; i
++) {
if (IN
[i
] < 0) join(i
, tar
, -IN
[i
]);
else {
join(src
, i
, IN
[i
]);
flow
+= IN
[i
];
}
}
int ans
= maxflow(src
, tar
);
if (flow
== ans
) {
puts("YES");
for (int i
= 1; i
<= m
; i
++) printf("%d\n", a
[i
].l
+ E
[i
* 2 - 1].len
);
} else puts("NO");
return 0;
}
有源汇上下界最大流
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int LEN
= 1e5 + 5;
const int oo
= (1LL << 31) - 1;
namespace DINIC
{
int tot
, n
, m
, src
, tar
, qh
, qt
, cnt
, s
, t
, S
, T
;
int ans
, flow
;
struct edge
{
int vet
, next
, len
;
} E
[LEN
* 2];
int dis
[LEN
], gap
[LEN
], head
[LEN
], cur
[LEN
], q
[LEN
], vis
[LEN
], IN
[LEN
];
void add(int u
, int v
, int c
) {
E
[++tot
] = (edge
){v
, head
[u
], c
};
head
[u
] = tot
;
}
void join(int u
, int v
, int c
) {
add(u
, v
, c
);
add(v
, u
, 0);
}
void init() {
tot
= -1;
for (int i
= 1; i
<= cnt
; i
++) head
[i
] = -1;
}
bool bfs() {
for (int i
= 1; i
<= cnt
; i
++) dis
[i
] = 0;
qh
= qt
= 0;
q
[++qt
] = src
;
dis
[src
] = 1;
while (qh
< qt
) {
int u
= q
[++qh
];
for (int e
= head
[u
]; e
!= -1; e
= E
[e
].next
) {
int v
= E
[e
].vet
;
if (E
[e
].len
&& !dis
[v
]) {
dis
[v
] = dis
[u
] + 1;
if (v
== tar
) return 1;
q
[++qt
] = v
;
}
}
}
return dis
[tar
];
}
int dfs(int u
, int aug
) {
if (u
== tar
|| !aug
) return aug
;
int tmp
= 0;
for (int &e
= cur
[u
]; e
!= -1; e
= E
[e
].next
) {
int v
= E
[e
].vet
;
if (dis
[v
] == dis
[u
] + 1) {
if (tmp
= dfs(v
, min(aug
, E
[e
].len
))) {
E
[e
].len
-= tmp
;
E
[e
^ 1].len
+= tmp
;
return tmp
;
}
}
}
return 0;
}
int maxflow(int s
, int t
) {
src
= s
, tar
= t
;
int res
= 0, flow
= 0;
while (bfs()) {
for (int i
= 1; i
<= cnt
; i
++) cur
[i
] = head
[i
];
while (flow
= dfs(src
, oo
)) res
+= flow
;
}
return res
;
}
}
using namespace DINIC
;
int main() {
scanf("%d %d %d %d", &n
, &m
, &s
, &t
);
cnt
= n
;
S
= ++cnt
, T
= ++cnt
;
init();
for (int i
= 1; i
<= m
; i
++) {
int x
, y
, l
, r
;
scanf("%d %d %d %d", &x
, &y
, &l
, &r
);
join(x
, y
, r
- l
);
IN
[y
] += l
, IN
[x
] -= l
;
}
for (int i
= 1; i
<= n
; i
++) {
if (IN
[i
] < 0) join(i
, T
, -IN
[i
]);
else if (IN
[i
] > 0) {
flow
+= IN
[i
];
join(S
, i
, IN
[i
]);
}
}
join(t
, s
, oo
);
ans
= maxflow(S
, T
);
if (ans
!= flow
) puts("please go home to sleep");
else {
ans
= maxflow(s
, t
);
printf("%lld\n", ans
);
}
return 0;
}
有源汇上下界最小流
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int LEN
= 2e5 + 5;
const int oo
= (1LL << 31) - 1;
namespace DINIC
{
int tot
, n
, m
, src
, tar
, qh
, qt
, cnt
, s
, t
, S
, T
, ans
, flow
;
struct edge
{
int vet
, next
, len
;
} E
[LEN
* 2];
int dis
[LEN
], gap
[LEN
], head
[LEN
], cur
[LEN
], q
[LEN
], vis
[LEN
], IN
[LEN
];
void add(int u
, int v
, int c
) {
E
[++tot
] = (edge
){v
, head
[u
], c
};
head
[u
] = tot
;
}
void join(int u
, int v
, int c
) {
add(u
, v
, c
);
add(v
, u
, 0);
}
void init() {
tot
= -1;
for (int i
= 1; i
<= cnt
; i
++) head
[i
] = -1;
}
bool bfs() {
for (int i
= 1; i
<= cnt
; i
++) dis
[i
] = 0;
qh
= qt
= 0;
q
[++qt
] = src
;
dis
[src
] = 1;
while (qh
< qt
) {
int u
= q
[++qh
];
for (int e
= head
[u
]; e
!= -1; e
= E
[e
].next
) {
int v
= E
[e
].vet
;
if (E
[e
].len
&& !dis
[v
]) {
dis
[v
] = dis
[u
] + 1;
if (v
== tar
) return 1;
q
[++qt
] = v
;
}
}
}
return dis
[tar
];
}
int dfs(int u
, int aug
) {
if (u
== tar
|| !aug
) return aug
;
int tmp
= 0;
for (int &e
= cur
[u
]; e
!= -1; e
= E
[e
].next
) {
int v
= E
[e
].vet
;
if (dis
[v
] == dis
[u
] + 1) {
if (tmp
= dfs(v
, min(aug
, E
[e
].len
))) {
E
[e
].len
-= tmp
;
E
[e
^ 1].len
+= tmp
;
return tmp
;
}
}
}
return 0;
}
int maxflow(int s
, int t
) {
src
= s
, tar
= t
;
int res
= 0, flow
= 0;
while (bfs()) {
for (int i
= 1; i
<= cnt
; i
++) cur
[i
] = head
[i
];
while (flow
= dfs(src
, oo
)) res
+= flow
;
}
return res
;
}
}
using namespace DINIC
;
int main() {
scanf("%d %d %d %d", &n
, &m
, &s
, &t
);
cnt
= n
;
S
= ++cnt
, T
= ++cnt
;
init();
for (int i
= 1; i
<= m
; i
++) {
int x
, y
, l
, r
;
scanf("%d %d %d %d", &x
, &y
, &l
, &r
);
join(x
, y
, r
- l
);
IN
[y
] += l
, IN
[x
] -= l
;
}
for (int i
= 1; i
<= n
; i
++) {
if (IN
[i
] < 0) join(i
, T
, -IN
[i
]);
else if (IN
[i
] > 0) {
flow
+= IN
[i
];
join(S
, i
, IN
[i
]);
}
}
ans
= maxflow(S
, T
);
flow
-= ans
;
join(t
, s
, oo
);
ans
= maxflow(S
, T
);
if (ans
!= flow
) puts("please go home to sleep");
else printf("%d\n", ans
);
return 0;
}
