- EK
动能算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
const int M=100050,N=10050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,pre[N],d[N];
struct edge{int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int u,int v,int cap)
{
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt++].cap=cap;
}
void update(int x,int to,int flow)
{
for(int i=x;i!=to;i=e[pre[i]^1].to)
{
e[pre[i]].flow+=flow;
e[pre[i]^1].flow-=flow;
}
}
int bfs(int s,int t)
{
while (!Q.empty()) Q.pop();
for(int i=1;i<=n;i++) d[i]=0;
d[s]=INF,Q.push(s);
while (!Q.empty()&&!d[t])
{
int x=Q.front();Q.pop();
for(int i=head[x];~i;i=e[i].next)
{
int to=e[i].to;
if (!d[to]&&e[i].flow<e[i].cap)
{
pre[to]=i;
d[to]=min(d[x],e[i].cap-e[i].flow);
Q.push(to);
}
}
}
return d[t];
}
int EK(int s,int t)
{
int ret=0,new_flow;
while (new_flow=bfs(s,t))
{
ret+=new_flow;
update(t,s,new_flow);
}
return ret;
}
int main()
{
n=read(),m=read();
st=read(),ed=read();
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
add(u,v,read());
add(v,u,0);
}
printf("%d",EK(st,ed));
return 0;
}
- Dinic
比EK快很多的Dinic1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
using namespace std;
const int M=120050,N=10050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,d[N],cur[N];
struct edge{int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int u,int v,int cap)
{
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt++].cap=cap;
}
int bfs(int s,int t)
{
while (!Q.empty()) Q.pop();
for(int i=1;i<=n;i++) d[i]=0;
d[s]=1,Q.push(s);
while (!Q.empty()&&!d[t])
{
int x=Q.front();Q.pop();
for(int i=head[x];~i;i=e[i].next)
{
int to=e[i].to;
if (e[i].flow<e[i].cap&&!d[to])
{
d[to]=d[x]+1;
Q.push(to);
}
}
}
return d[t];
}
int dfs(int x,int t,int flow)
{
if (!flow||x==t) return flow;
int ret=0,new_flow;
for(int &i=cur[x];~i&&flow;i=e[i].next)
{
int to=e[i].to;
if (d[x]+1==d[to])
{
new_flow=dfs(to,t,min(flow,e[i].cap-e[i].flow));
e[i].flow+=new_flow;
e[i^1].flow-=new_flow;
ret+=new_flow;
flow-=new_flow;
}
}
return ret;
}
int Dinic(int s,int t)
{
int ret=0;
while (bfs(s,t))
{
for(int i=1;i<=n;i++) cur[i]=head[i];
ret+=dfs(s,t,INF);
}
return ret;
}
int main()
{
n=read(),m=read();
st=read(),ed=read();
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
add(u,v,read());
add(v,u,0);
}
printf("%d",Dinic(st,ed));
return 0;
}
- ISAP
ISAP+GAP优化+当前弧优化1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
using namespace std;
const int M=100050,N=10050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,d[N],num[N],pre[N],cur[N];
struct edge{int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int u,int v,int cap)
{
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt++].cap=cap;
}
void bfs(int s)
{
for(int i=1;i<=n;i++) d[i]=n;
d[s]=0,Q.push(s);
while (!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=head[x];~i;i=e[i].next)
{
int to=e[i].to;
if (d[x]+1<d[to]&&e[i^1].cap)
{
d[to]=d[x]+1;
Q.push(to);
}
}
}
}
int update(int x,int to)
{
int ret=INF;
for(int i=x;i!=to;i=e[pre[i]^1].to)
ret=min(ret,e[pre[i]].cap-e[pre[i]].flow);
for(int i=x;i!=to;i=e[pre[i]^1].to)
{
e[pre[i]].flow+=ret;
e[pre[i]^1].flow-=ret;
}
return ret;
}
int ISAP(int s,int t)
{
bfs(t);
for(int i=1;i<=n;i++) num[d[i]]++;
for(int i=1;i<=n;i++) cur[i]=head[i];
int ret=0,x=s;
while (d[s]<=n)
{
if (x==t) ret+=update(t,s),x=s;
int flag=0;
for(int i=cur[x];~i;i=e[i].next)
{
int to=e[i].to;
if (d[x]==d[to]+1&&e[i].flow<e[i].cap)
{
flag=1,cur[x]=i;
pre[x=to]=i;
break;
}
}
if (!flag)
{
int idx=n-1;
for(int i=head[x];~i;i=e[i].next)
if (e[i].flow<e[i].cap)
idx=min(idx,d[e[i].to]);
if (--num[d[x]]==0) break;
num[d[x]=idx+1]++;
cur[x]=head[x];
if (x!=s) x=e[pre[x]^1].to;
}
}
return ret;
}
int main()
{
n=read(),m=read();
st=read(),ed=read();
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
add(u,v,read());
add(v,u,0);
}
printf("%d",ISAP(st,ed));
return 0;
}
- 最小费用最大流
Min_Cost_Max_Flow1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using namespace std;
const int M=50050,N=5050,INF=1<<25;
int n,m,st,ed,head[N],cnt=0,pre[N],d[N],c[N],cost=0,inq[N];
struct edge{int to,next,flow,cap,cost;} e[M<<1];
queue<int> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int u,int v,int cap,int cost)
{
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].cost=cost;
e[cnt++].cap=cap;
}
void update(int x,int to,int flow)
{
for(int i=x;i!=to;i=e[pre[i]^1].to)
{
e[pre[i]].flow+=flow;
e[pre[i]^1].flow-=flow;
}
}
int SPFA(int s,int t)
{
for(int i=1;i<=n;i++) d[i]=INF,c[i]=0;
d[s]=0,c[s]=INF,Q.push(s);
while (!Q.empty())
{
int x=Q.front();
Q.pop(),inq[x]=0;
for(int i=head[x];~i;i=e[i].next)
{
int to=e[i].to,cost=e[i].cost;
if (e[i].flow<e[i].cap&&d[x]+cost<d[to])
{
d[to]=d[x]+cost;
pre[to]=i;
c[to]=min(c[x],e[i].cap-e[i].flow);
if (!inq[to]) Q.push(to),inq[to]=1;
}
}
}
return c[t];
}
int MCMF(int s,int t)
{
int ret=0,new_flow;
while (new_flow=SPFA(s,t))
{
ret+=new_flow;
cost+=new_flow*d[t];
update(t,s,new_flow);
}
return ret;
}
int main()
{
n=read(),m=read();
st=read(),ed=read();
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
int cap=read(),cost=read();
add(u,v,cap,cost);
add(v,u,0,-cost);
}
int max_flow=MCMF(st,ed);
printf("%d %d",max_flow,cost);
return 0;
}