标签：总结 易错 val int flow while edge 模板 dis
一、最大流
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 300,MM = 5e3 + 8,INF = 0x7f7f7f7f;
int n,m,s,t;
int dis[NN];
queue<int> q;
inline int read(){
register int res = 0,flag = 1;
register char c = getchar();
while(!isdigit(c)){
if(c == '-') flag = -1;
c = getchar();
}
while(isdigit(c)){
res = res * 10 + c - '0';
c = getchar();
}
return res * flag;
}
struct Edge{
int to,next,val;
}edge[MM << 1];
int head[NN],cnt,pre[NN];
void init(){
cnt = 1;
for(int i = 1; i <= n+1; i++)head[i] = pre[i] = -1;//head数组和pre数组都要赋初值为-1
}
void add_edge(int u,int v,int w){
edge[++cnt] = {v,head[u],w};
head[u] = pre[u] = cnt;
}
int bfs(){
memset(dis,0,sizeof(dis));
while(!q.empty())q.pop();//记得初始化清空队列
q.push(s);dis[s] = 1;head[s] = pre[s];
while(!q.empty()){
int u = q.front();q.pop();
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to,w = edge[i].val;//edge[i].to不要写成next
if(w && !dis[v]){
q.push(v);
head[v] = pre[v];//head初始化
dis[v] = dis[u] + 1;
if(v == t)return 1;
}
}
}
return 0;
}
ll dinic(int u,int flow){
if(u == t)return flow;
int rest = flow;
//if(!rest) return 0;
for(int &i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to,w = edge[i].val;
if(w && dis[u] + 1 == dis[v]){
int k = dinic(v,min(rest,w));//rest不要写成flow
if(!k) dis[v] = 0;
edge[i].val -= k;
edge[i^1].val += k;//^1不能忘
rest -= k;
}
if(!rest)break;//当前弧优化的rest在后面判定
}
return flow - rest;
}
int main(){
n = read(),m = read(),s = read(),t = read();
init();
for(int i = 1,u,v,w; i <= m; ++i){
u = read(),v = read(),w = read();
add_edge(u,v,w);add_edge(v,u,0);
}
ll ans = 0,flow = 0;
while(bfs()){
while(flow = dinic(s,INF)) ans += flow;//少掉while就会慢的一匹
}
printf("%lld",ans);
}
二、最小费用最大流
#include<bits/stdc++.h>
using namespace std;
const int NN = 5e3 + 8,MM = 1e5 + 8,INF = 0x3f3f3f3f;
int n,m,s,t,cost;
bool vis[NN];
inline int read(){
register int res = 0,flag = 1;
register char c = getchar();
while(!isdigit(c)){
if(c == '0')flag = -1;c = getchar();
}
while(isdigit(c)){
res = res * 10 + c - '0';
c = getchar();
}
return res * flag;
}
struct Edge{
int to,next,val,water;
}edge[MM << 1];
int head[NN],pre[NN],cnt;
void init(){
cnt = 1;
for(int i = 1; i <= n; ++i)head[i] = pre[i] = -1;//两个数组都要初始化
}
void add_edge(int u,int v,int w,int flow){
edge[++cnt] = {v,head[u],w,flow};
head[u] = pre[u] = cnt;//两个数组都要更新
}
queue<int> q;
int dis[NN];
bool SPFA(){
memset(dis,0x3f,sizeof(dis));
vis[s] = 1;
while(!q.empty())q.pop();
q.push(s);head[s] = pre[s];dis[s] = 0;//初始化一个都不能忘，特别是vis
while(!q.empty()){
int u = q.front();q.pop();
vis[u] = 0;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to,water = edge[i].water,val = edge[i].val;
if(water && dis[v] > dis[u] + val){
dis[v] = dis[u] + val;
head[v] = pre[v];
if(!vis[v])q.push(v),vis[v] = 1;
}
}
}
return dis[t] != INF;//这该是只能放后面的吧
}
int dfs(int u,int flow){
if(u == t)return flow;
int rest = flow;
vis[u] = 1;
if(!rest) return 0;
for(int &i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to,water = edge[i].water,val = edge[i].val;
if(!vis[v] && dis[u] + val == dis[v] && water){
int x = dfs(v,min(water,rest));//rest不能写成flow
if(!x) dis[v] = 0;
cost += x * val;
rest -= x;
edge[i].water -= x;edge[i^1].water += x;
}
if(!rest)break;
}
vis[u] = 0;
return flow - rest;
}
int main(){
n = read(); m = read(); s = read(); t = read();
init();
for(int i = 1,u,v,w,f; i <= m; ++i){
u = read();v = read();f = read();w = read();
add_edge(u,v,w,f);
add_edge(v,u,-w,0);//反边的代价为负，容量为0
}
int ans = 0,flow = 0;
while(SPFA()){
while(flow = dfs(s,INF)) ans += flow;
}
printf("%d %d",ans,cost);
}
三、有源汇有上下界最大流
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, NN = 1e6 + 8, MM = 1e6 + 8;
int n,m,s1,s2,t1,t2,S,T;
int ds[NN];
struct Edge{
int to,next,val;
}edge[MM << 1];
int head[NN],cnt,pre[NN];
void init(){
cnt = 1;
memset(ds,0,sizeof(ds));
for(int i = 0; i < NN; ++i)head[i] = pre[i] = -1;
}
void add_edge(int u,int v,int w){
edge[++cnt] = {v,head[u],w};
head[u] = pre[u] = cnt;
}
queue<int> q;
int sum,e;
int dis[NN];
bool bfs() {
while(!q.empty())q.pop();
memset(dis,0,sizeof(dis));
q.push(S);head[S] = pre[S];dis[S] = 1;
while(!q.empty()){
int u = q.front();q.pop();
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to,val = edge[i].val;
if(!dis[v] && val){
dis[v] = dis[u] + 1;
head[v] = pre[v];
if(v == T) return 1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow){
if(u == T) return flow;
int rest = flow;
for(int &i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to,val = edge[i].val;
if(val && dis[u] + 1 == dis[v]){
int k = dfs(v,min(rest,val));
if(!k) dis[v] = 0;
edge[i].val -= k;edge[i^1].val += k;
rest -= k;
}
if(!rest)break;
}
return flow - rest;
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
s1 = n + m + 1;t1 = n + m + 2;s2 = n + m + 3;t2 = n + m + 4;
for(int i = n + 1,v; i <= m + n; ++i){
scanf("%d",&v);
ds[t1] += v; ds[i] -= v;
add_edge(i,t1,INF-v);//少女向汇点连边
add_edge(t1,i,0);
}
for(int i = 1,c,w; i <= n; ++i){
scanf("%d%d",&c,&w);
add_edge(s1,i,w);
add_edge(i,s1,0);
for(int j = 1,x,l,r; j <= c; ++j){
scanf("%d%d%d",&x,&l,&r);
++x;
add_edge(i,x + n,r - l);//天数向少女连边
add_edge(x + n,i,0);
ds[i] -= l;
ds[x + n] += l;
}
}
int ans = 0;
for(int i = 1; i <= n + m + 2; i++) {
if(ds[i] > 0) {
ans += ds[i];
add_edge(s2, i, ds[i]);
add_edge(i, s2, 0);
}
else if(ds[i] < 0){
add_edge(i, t2, -ds[i]);
add_edge(t2, i, 0);
}
}
add_edge(t1,s1,INF);
add_edge(s1,t1,0);
int ans1 = 0,ans2 = 0,flow;
S = s2;T = t2;
while(bfs()){
while(flow = dfs(S,INF)){
ans1 += flow;
}
}
if(ans1 != ans)printf("-1\n\n");
else{
int res=edge[cnt-2].val;
edge[cnt-1].val=0, edge[cnt-2].val=0;
S=s1, T=t1;
while(bfs())
while(flow = dfs(S,INF)) ans2 += flow;
printf("%d\n\n",ans2);
}
}
}
标签：总结,
易错,
val,
int,
flow,
while,
edge,
模板,
dis
From： https://www.cnblogs.com/rickylin/p/17049582.html