最大フローテンプレート
6699 ワード
Edmods_Karpアルゴリズム
時間複雑度:O(n*m*m)
Dinicアルゴリズム:
複雑度:O(n*n*m)
SPAアルゴリズム:
複雑度O(n*n*m)
複雑さはDinicと同じですが、さまざまな最適化を経てDinicよりやや優れています.
時間複雑度:O(n*m*m)
//EK
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define CLR(arr, v) memset(arr, v, sizeof(arr))
#pragma warning (disable:4996)
using namespace std;
const int MaxE = 100 * 2; // 2
const int MaxV = 100;
const int INF = 1e9;
struct Graph
{
struct Vertex
{
int head;
}V[MaxV];
struct Edge
{
int v, c, f, next;
Edge(){};
Edge(int v, int c,int f, int next):v(v), c(c), f(f), next(next){}
}E[MaxE];
int top;
void init()
{
top = 0;
CLR(V, -1);
}
void addEdge(int u, int v, int c)
{
E[top] = Edge(v, c, 0, V[u].head);
V[u].head = top++;
E[top] = Edge(u, 0, 0, V[v].head);
V[v].head = top++;
}
};
Graph g;
int vexNum, edgeNum; // ,
int s, t; // ,
int path[MaxV]; //
int flow[MaxV]; //
bool bfs()
{
CLR(flow, 0); //
queue<int> Q;
Q.push(s);
flow[s] = INF;
while(!Q.empty())
{
int top = Q.front();
for(int i = g.V[top].head; i != -1; i = g.E[i].next)
{
int v = g.E[i].v;
if(g.E[i].f < g.E[i].c && !flow[v]) // !flow[v]
{
path[v] = i;
flow[v] = min(flow[top], g.E[i].c - g.E[i].f); //is flow[top]
if(v == t)
return true;
Q.push(v);
}
}
Q.pop();
}
return false;
}
int EK()
{
int i, maxFlow = 0;
while(bfs())
{
for(int v = t; v != s; v = g.E[i ^ 1].v) // i
{
i = path[v];
g.E[i].f += flow[t];
g.E[i ^ 1].f -= flow[t];
}
maxFlow += flow[t];
}
return maxFlow;
}
int main()
{
g.init(); //
scanf("%d %d", &vexNum, &edgeNum);
for(int i = 0; i < edgeNum; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
g.addEdge(u, v, w);
}
s = 1, t = vexNum;
printf("%d
", EK());
}
Dinicアルゴリズム:
複雑度:O(n*n*m)
//Dinic
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define CLR(arr, val) memset(arr, val, sizeof(arr))
#pragma warning(disable:4996)
using namespace std;
const int INF = 1e9;
const int MaxE = 100 * 2;
const int MaxV = 100;
struct Graph
{
struct Vertex
{
int head;
}V[MaxV];
struct Edge
{
int v, c, next;
Edge(int v,int c, int next):v(v), c(c), next(next){}
Edge(){}
}E[MaxE];
void init()
{
top = 0;
CLR(V, -1);
}
void addEdge(int u, int v, int c)
{
E[top] = Edge(v, c, V[u].head);
V[u].head = top++;
E[top] = Edge(u, 0, V[v].head);
V[v].head = top++;
}
int top;
};
int level[MaxV];
int path[MaxV];
int s, t;
Graph g;
bool bfs()
{
CLR(level, -1);
level[s] = 0;
queue<int>Q;
Q.push(s);
while(!Q.empty())
{
int top = Q.front();
for(int i = g.V[top].head; i != -1; i = g.E[i].next)
{
int v = g.E[i].v;
if(level[v] == -1 && g.E[i].c)
{
level[v] = level[top] + 1;
Q.push(v);
}
}
Q.pop();
}
return level[t] != -1;
}
int dfs(int cur, int c)
{
if(cur == t)
{
return c;
}
int sum = c;
for(int i = g.V[cur].head; i != -1; i = g.E[i].next)
{
int v = g.E[i].v;
if(g.E[i].c > 0 && level[v] == level[cur] + 1)
{
int a = dfs(v, min(c, g.E[i].c));
g.E[i].c -= a; // Dinic , spa
g.E[i ^ 1].c += a;
c -= a;
}
}
return sum - c;
}
int dinic()
{
int maxFlow = 0;
while(bfs())
{
maxFlow += dfs(1, INF);
}
return maxFlow;
}
int vexNum, edgeNum;
int main(){
g.init();
scanf("%d %d", &vexNum, &edgeNum);
for(int i = 0; i < edgeNum; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
g.addEdge(u, v, w);
}
s = 1, t = vexNum;
printf("%d
", dinic());
return 0;
}
SPAアルゴリズム:
複雑度O(n*n*m)
複雑さはDinicと同じですが、さまざまな最適化を経てDinicよりやや優れています.
//SPA
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
#define CLR(arr, val) memset(arr, val, sizeof(arr))
#pragma warning(disable:4996)
using namespace std;
const int MaxV = 1003;
const int MaxE = 10000 << 1;
const int INF = 1e9;
struct Graph
{
struct Vertex
{
int head;
}V[MaxV];
struct Edge
{
int v, c, f, next;
Edge(){}
Edge(int v,int c, int f, int next):v(v), c(c), f(f), next(next){}
}E[MaxE];
void init()
{
top = 0;
CLR(V, -1);
}
void addEdge(int u, int v,int w)
{
E[top] = Edge(v, w, 0, V[u].head);
V[u].head = top++;
E[top] = Edge(u, 0, 0, V[v].head);
V[v].head = top++;
}
int top;
};
int s, t, vexNum;
int h[MaxV],pre[MaxV],cur[MaxV],gap[MaxV];
Graph g;
void setHeight()
{
queue<int> Q;
CLR(h,-1);
CLR(gap,0);
h[t] = 0;
Q.push(t);
while(!Q.empty())
{
int v = Q.front();
Q.pop();
++gap[ h[v] ];
for(int i=g.V[v].head;i!=-1;i=g.E[i].next)
{
int u = g.E[i].v;
if(h[u] == -1)
{
h[u] = h[v]+1;
Q.push(u);
}
}
}
}
int sap()
{
setHeight(); //You can replace it with "CLR(d,0)" if you feel it trouble
int MaxFlow = 0, u = s;
int flow = INF;
memcpy(cur,g.V,sizeof(g.V)); //current arc
while(h[s] < vexNum)
{
int &i = cur[u]; //reference
for(;i!=-1;i=g.E[i].next)
{
int v = g.E[i].v;
if(g.E[i].c > g.E[i].f && h[u] == h[v]+1) //admissible arc
{
u = v;
pre[v] = i;
flow = min(flow,g.E[i].c-g.E[i].f);
if(u == t)
{
while(u != s)
{
int j = pre[u];
g.E[j].f += flow;
g.E[j^1].f -= flow;
u = g.E[j^1].v;
}
MaxFlow += flow;
flow = INF;
}
break;
}
}
if(i == -1) //there's no admissible arc.
{
if(--gap[ h[u] ] == 0)
break;
int dmin = vexNum-1;
cur[u] = g.V[u].head;
for(int j=g.V[u].head;j!=-1;j=g.E[j].next)
if(g.E[j].c > g.E[j].f) //not full arc
dmin = min(dmin,h[ g.E[j].v ]);
h[u] = dmin+1;
++gap[ h[u] ];
if(u != s)
u = g.E[ pre[u]^1 ].v;
}
}
return MaxFlow;
}
int main(){int ncase, tmp = 1;scanf("%d", &ncase);while(ncase--){g.init();scanf("%d %d", &vexNum, &edgeNum);while(edgeNum--){int u, v, w;scanf("%d %d %d", &u, &v, &w);g.addEdge(u, v, w);}s = 1, t = vexNum;printf("Case %d: %d", tmp++, sap());}return 0;}
すべての はHDU 3549に して かれています