题意：1是源点，m是汇点，求出来最大流量，没什么好说的就是练习最大流的模板题
**************************************************************
先用Edmonds-Karp的算法做一下试试吧
重边贡献了 1W，要加上所有的重边才算是两点间最大流量
***********************************************************************************************************************
/************************************/
/** 使用Edmonds-Karp 最短增广路算法*/
/** 邻接矩阵实现 */
/** 2015/8/7/9:39 */
/************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
///1是源点，M是汇点，N条边
int G[MAXN][MAXN], M, N;
int pre[MAXN];///记录每个点的前驱，也就是父节点
bool used[MAXN];
///s代表源点，e代表汇点,可以到达汇返回true，否则返回false
bool BFS(int s, int e)
{
memset(used, false, sizeof(used));
queue<int> Q;
Q.push(s);
used[s] = true;
while(Q.size())
{
s = Q.front();Q.pop();
if(s == e) return true;
for(int i=1; i<=M; i++)
{
if(G[s][i] && !used[i])
{
pre[i] = s;
used[i] = true;
Q.push(i);
}
}
}
return false;
}
int Karp(int s, int e)
{
int MaxFlow = 0;
while( BFS(s, e) == true )
{///如果有增量
int MinFlow = oo, v;
v = e;
while(v != s)
{///求出来路径上最小流量
MinFlow = min(MinFlow, G[pre[v]][v]);
v = pre[v];
}
MaxFlow += MinFlow;
v = e;
while(v != s)
{///边上的所有点减去最小流量，反边增加流量
G[pre[v]][v] -= MinFlow;
G[v][pre[v]] += MinFlow;
v = pre[v];
}
}
return MaxFlow;
}
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, c;
memset(G, false, sizeof(G));
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &c);
G[u][v] += c;///有重边，两点间应该算上所有边
}
printf("%d ", Karp(1, M));
}
return 0;
}
/** 使用Edmonds-Karp 最短增广路算法*/
/** 邻接矩阵实现 */
/** 2015/8/7/9:39 */
/************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
///1是源点，M是汇点，N条边
int G[MAXN][MAXN], M, N;
int pre[MAXN];///记录每个点的前驱，也就是父节点
bool used[MAXN];
///s代表源点，e代表汇点,可以到达汇返回true，否则返回false
bool BFS(int s, int e)
{
memset(used, false, sizeof(used));
queue<int> Q;
Q.push(s);
used[s] = true;
while(Q.size())
{
s = Q.front();Q.pop();
if(s == e) return true;
for(int i=1; i<=M; i++)
{
if(G[s][i] && !used[i])
{
pre[i] = s;
used[i] = true;
Q.push(i);
}
}
}
return false;
}
int Karp(int s, int e)
{
int MaxFlow = 0;
while( BFS(s, e) == true )
{///如果有增量
int MinFlow = oo, v;
v = e;
while(v != s)
{///求出来路径上最小流量
MinFlow = min(MinFlow, G[pre[v]][v]);
v = pre[v];
}
MaxFlow += MinFlow;
v = e;
while(v != s)
{///边上的所有点减去最小流量，反边增加流量
G[pre[v]][v] -= MinFlow;
G[v][pre[v]] += MinFlow;
v = pre[v];
}
}
return MaxFlow;
}
int main()
{
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, c;
memset(G, false, sizeof(G));
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &c);
G[u][v] += c;///有重边，两点间应该算上所有边
}
printf("%d ", Karp(1, M));
}
return 0;
}
邻接表实现
***********************************************************************************************************************
/************************************/
/// 使用Edmonds-Karp 最短增广路算法
/// 邻接表实现
/// 2015年8月7日10:13:55
/************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
struct Edge{int u, v, Flow, next;}e[MAXN<<1];
int Head[MAXN], cnt;
int pre[MAXN], used[MAXN];
void InIt()
{
memset(Head, -1, sizeof(Head));
cnt = 0;
}
void AddEdge(int u, int v, int Flow)
{
e[cnt].u = u;
e[cnt].v = v;
e[cnt].Flow = Flow;
e[cnt].next = Head[u];
Head[u] = cnt++;
}
bool BFS(int s, int End)
{
memset(used, false, sizeof(used));
memset(pre, -1, sizeof(pre));
queue<int> Q;
Q.push(s);
used[s] = true;
while(Q.size())
{
s = Q.front();Q.pop();
if(s == End)return true;
for(int i=Head[s]; i!=-1; i=e[i].next)
{
if(e[i].Flow && used[e[i].v] == false)
{
used[e[i].v] = true;
pre[e[i].v] = i;///记录的是上面的边的位置
Q.push(e[i].v);
}
}
}
return false;
}
int Karp(int s, int End)
{
int MaxFlow = 0;
while(BFS(s, End) == true)
{
int MinFlow = oo, v;
v = pre[End];
while(v != -1)
{
MinFlow = min(MinFlow, e[v].Flow);
v = pre[e[v].u];///上个点来的位置
}
MaxFlow += MinFlow;
v = pre[End];
while(v != -1)
{
e[v].Flow -= MinFlow;
e[v^1].Flow += MinFlow;
v = pre[e[v].u];
}
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, Flow;
InIt();
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &Flow);
AddEdge(u, v, Flow);
AddEdge(v, u, 0);///先添加一条反边的流量是0
}
printf("%d ", Karp(1, M));
}
return 0;
}
/// 使用Edmonds-Karp 最短增广路算法
/// 邻接表实现
/// 2015年8月7日10:13:55
/************************************/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
struct Edge{int u, v, Flow, next;}e[MAXN<<1];
int Head[MAXN], cnt;
int pre[MAXN], used[MAXN];
void InIt()
{
memset(Head, -1, sizeof(Head));
cnt = 0;
}
void AddEdge(int u, int v, int Flow)
{
e[cnt].u = u;
e[cnt].v = v;
e[cnt].Flow = Flow;
e[cnt].next = Head[u];
Head[u] = cnt++;
}
bool BFS(int s, int End)
{
memset(used, false, sizeof(used));
memset(pre, -1, sizeof(pre));
queue<int> Q;
Q.push(s);
used[s] = true;
while(Q.size())
{
s = Q.front();Q.pop();
if(s == End)return true;
for(int i=Head[s]; i!=-1; i=e[i].next)
{
if(e[i].Flow && used[e[i].v] == false)
{
used[e[i].v] = true;
pre[e[i].v] = i;///记录的是上面的边的位置
Q.push(e[i].v);
}
}
}
return false;
}
int Karp(int s, int End)
{
int MaxFlow = 0;
while(BFS(s, End) == true)
{
int MinFlow = oo, v;
v = pre[End];
while(v != -1)
{
MinFlow = min(MinFlow, e[v].Flow);
v = pre[e[v].u];///上个点来的位置
}
MaxFlow += MinFlow;
v = pre[End];
while(v != -1)
{
e[v].Flow -= MinFlow;
e[v^1].Flow += MinFlow;
v = pre[e[v].u];
}
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, Flow;
InIt();
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &Flow);
AddEdge(u, v, Flow);
AddEdge(v, u, 0);///先添加一条反边的流量是0
}
printf("%d ", Karp(1, M));
}
return 0;
}
Dinic实现
************************************************************************************************************************
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
struct Edge{int u, v, flow, next;}edge[MAXN*MAXN];
int Head[MAXN], cnt;
int layer[MAXN];///分层
int Start, End;///源点汇点
void AddEdge(int u, int v, int flow)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].flow = flow;
edge[cnt].next = Head[u];
Head[u] = cnt++;
}
bool BfsLayer()///使用广搜进行分层
{
bool used[MAXN]={0};queue<int> Q;
memset(layer, -1, sizeof(layer));
Q.push(Start);
used[Start] = true;
layer[Start] = 0;
while(Q.size())
{
int s = Q.front();Q.pop();
if(s == End)return true;
for(int i=Head[s]; i!=-1; i=edge[i].next)
{
int v = edge[i].v;
if(edge[i].flow && !used[v])
{
used[v] = true;
layer[v] = layer[s] + 1;
Q.push(v);
}
}
}
return false;
}
int dfs(int u, int MaxFlow)
{///MaxFlow 记录的是这条路径上能经过的最大流量
if(u == End)return MaxFlow;
int uFlow = 0;///这个点最多能经过多少流量
for(int i=Head[u]; i!=-1; i=edge[i].next)
{
int v = edge[i].v, flow = edge[i].flow;
if(layer[v]-1 == layer[u] && flow)
{
flow = min(MaxFlow-uFlow, flow);
flow = dfs(v, flow);
edge[i].flow -= flow;
edge[i^1].flow += flow;
uFlow += flow;
if(uFlow == MaxFlow)
break;///已经等于最大流量的时候注意结束
}
}
return uFlow;
}
int Dinic()///用dinic算法求最大流
{
int MaxFlow = 0;
while(BfsLayer() == true)
{
MaxFlow += dfs(Start, oo);
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, flow;
Start = 1, End = M, cnt = 0;
memset(Head, -1, sizeof(Head));
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &flow);
AddEdge(u, v, flow);
AddEdge(v, u, 0);
}
printf("%d ", Dinic());
}
return 0;
}
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
struct Edge{int u, v, flow, next;}edge[MAXN*MAXN];
int Head[MAXN], cnt;
int layer[MAXN];///分层
int Start, End;///源点汇点
void AddEdge(int u, int v, int flow)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].flow = flow;
edge[cnt].next = Head[u];
Head[u] = cnt++;
}
bool BfsLayer()///使用广搜进行分层
{
bool used[MAXN]={0};queue<int> Q;
memset(layer, -1, sizeof(layer));
Q.push(Start);
used[Start] = true;
layer[Start] = 0;
while(Q.size())
{
int s = Q.front();Q.pop();
if(s == End)return true;
for(int i=Head[s]; i!=-1; i=edge[i].next)
{
int v = edge[i].v;
if(edge[i].flow && !used[v])
{
used[v] = true;
layer[v] = layer[s] + 1;
Q.push(v);
}
}
}
return false;
}
int dfs(int u, int MaxFlow)
{///MaxFlow 记录的是这条路径上能经过的最大流量
if(u == End)return MaxFlow;
int uFlow = 0;///这个点最多能经过多少流量
for(int i=Head[u]; i!=-1; i=edge[i].next)
{
int v = edge[i].v, flow = edge[i].flow;
if(layer[v]-1 == layer[u] && flow)
{
flow = min(MaxFlow-uFlow, flow);
flow = dfs(v, flow);
edge[i].flow -= flow;
edge[i^1].flow += flow;
uFlow += flow;
if(uFlow == MaxFlow)
break;///已经等于最大流量的时候注意结束
}
}
return uFlow;
}
int Dinic()///用dinic算法求最大流
{
int MaxFlow = 0;
while(BfsLayer() == true)
{
MaxFlow += dfs(Start, oo);
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, flow;
Start = 1, End = M, cnt = 0;
memset(Head, -1, sizeof(Head));
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &flow);
AddEdge(u, v, flow);
AddEdge(v, u, 0);
}
printf("%d ", Dinic());
}
return 0;
}
SAP实现
*************************************************************************************************************************
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
struct Edge{int u, v, flow, next;}edge[MAXN*MAXN];
int Head[MAXN], cnt;
int Layer[MAXN];///分层
int start, End;///源点汇点
int cur[MAXN], Stack[MAXN],gap[MAXN];
int sumV;///节点的总个数
void AddEdge(int u, int v, int flow)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].flow = flow;
edge[cnt].next = Head[u];
Head[u] = cnt++;
}
void BFS()
{
memset(Layer, -1, sizeof(Layer));
memset(gap, 0, sizeof(gap));
queue<int> Q;
Q.push(End);
Layer[End] = 0, gap[0] = 1;
while(Q.size())
{
int u = Q.front();
Q.pop();
for(int j=Head[u]; j!=-1; j=edge[j].next)
{
int v = edge[j].v;
if(Layer[v] == -1)
{
Layer[v] = Layer[u] + 1;
gap[Layer[v]]++;
Q.push(v);
}
}
}
}
int SAP()
{
int j, top=0, u = start, MaxFlow=0;
BFS();
memcpy(cur, Head, sizeof(Head));
while(Layer[start] < sumV)
{///源点的层次小于总结点数,汇点是0层
if(u == End)
{
int MinFlow = oo, location;///记录下最小流量边的位置，出栈时候用
for(j=0; j<top; j++)
{
int i = Stack[j];
if(MinFlow > edge[i].flow)
{
MinFlow = edge[i].flow;
location = j;
}
}
for(j=0; j<top; j++)
{///所有的边减去路径上的最小流量
int i = Stack[j];
edge[i].flow -= MinFlow;
edge[i^1].flow += MinFlow;
}
MaxFlow += MinFlow;
top = location;///退栈
u = edge[Stack[top]].u;
}
else if(gap[Layer[u]-1] == 0)
break;///u所在的层下面的层没有了，出现了断层，也就没有了可行弧
for(j=cur[u]; j!=-1; j=edge[j].next)
{///如果u有可行弧就停止
if(Layer[u]==Layer[edge[j].v]+1 && edge[j].flow)
break;
}
if(j != -1)
{///找到了可行弧
cur[u] = j;///u点的可行弧是j
Stack[top++] = j;///记录下这条边
u = edge[j].v;
}
else
{///没有找到可行弧，修改标号
int MinIndex = sumV;
for(j=Head[u]; j!=-1; j=edge[j].next)
{///查找与u相连的最小的层是多少
if(edge[j].flow && MinIndex > Layer[edge[j].v])
{///记录下这条可行弧,下次可以直接访问这条边
MinIndex = Layer[edge[j].v];
cur[u] = j;
}
}
gap[Layer[u]] -= 1;///u改变层，所以u原来所在层的点数减去1
Layer[u] = MinIndex + 1;
gap[Layer[u]] += 1;
if(u != start)
{///返回上一层
u = edge[Stack[--top]].u;
}
}
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, flow;
sumV = M;
start = 1, End = M, cnt = 0;
memset(Head, -1, sizeof(Head));
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &flow);
AddEdge(u, v, flow);
AddEdge(v, u, 0);
}
printf("%d ", SAP());
}
return 0;
}
#include<string.h>
#include<queue>
using namespace std;
const int MAXN = 205;
const int oo = 1e9+7;
struct Edge{int u, v, flow, next;}edge[MAXN*MAXN];
int Head[MAXN], cnt;
int Layer[MAXN];///分层
int start, End;///源点汇点
int cur[MAXN], Stack[MAXN],gap[MAXN];
int sumV;///节点的总个数
void AddEdge(int u, int v, int flow)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].flow = flow;
edge[cnt].next = Head[u];
Head[u] = cnt++;
}
void BFS()
{
memset(Layer, -1, sizeof(Layer));
memset(gap, 0, sizeof(gap));
queue<int> Q;
Q.push(End);
Layer[End] = 0, gap[0] = 1;
while(Q.size())
{
int u = Q.front();
Q.pop();
for(int j=Head[u]; j!=-1; j=edge[j].next)
{
int v = edge[j].v;
if(Layer[v] == -1)
{
Layer[v] = Layer[u] + 1;
gap[Layer[v]]++;
Q.push(v);
}
}
}
}
int SAP()
{
int j, top=0, u = start, MaxFlow=0;
BFS();
memcpy(cur, Head, sizeof(Head));
while(Layer[start] < sumV)
{///源点的层次小于总结点数,汇点是0层
if(u == End)
{
int MinFlow = oo, location;///记录下最小流量边的位置，出栈时候用
for(j=0; j<top; j++)
{
int i = Stack[j];
if(MinFlow > edge[i].flow)
{
MinFlow = edge[i].flow;
location = j;
}
}
for(j=0; j<top; j++)
{///所有的边减去路径上的最小流量
int i = Stack[j];
edge[i].flow -= MinFlow;
edge[i^1].flow += MinFlow;
}
MaxFlow += MinFlow;
top = location;///退栈
u = edge[Stack[top]].u;
}
else if(gap[Layer[u]-1] == 0)
break;///u所在的层下面的层没有了，出现了断层，也就没有了可行弧
for(j=cur[u]; j!=-1; j=edge[j].next)
{///如果u有可行弧就停止
if(Layer[u]==Layer[edge[j].v]+1 && edge[j].flow)
break;
}
if(j != -1)
{///找到了可行弧
cur[u] = j;///u点的可行弧是j
Stack[top++] = j;///记录下这条边
u = edge[j].v;
}
else
{///没有找到可行弧，修改标号
int MinIndex = sumV;
for(j=Head[u]; j!=-1; j=edge[j].next)
{///查找与u相连的最小的层是多少
if(edge[j].flow && MinIndex > Layer[edge[j].v])
{///记录下这条可行弧,下次可以直接访问这条边
MinIndex = Layer[edge[j].v];
cur[u] = j;
}
}
gap[Layer[u]] -= 1;///u改变层，所以u原来所在层的点数减去1
Layer[u] = MinIndex + 1;
gap[Layer[u]] += 1;
if(u != start)
{///返回上一层
u = edge[Stack[--top]].u;
}
}
}
return MaxFlow;
}
int main()
{
int N, M;
while(scanf("%d%d", &N, &M) != EOF)
{
int i, u, v, flow;
sumV = M;
start = 1, End = M, cnt = 0;
memset(Head, -1, sizeof(Head));
for(i=1; i<=N; i++)
{
scanf("%d%d%d", &u, &v, &flow);
AddEdge(u, v, flow);
AddEdge(v, u, 0);
}
printf("%d ", SAP());
}
return 0;
}