题目链接:http://poj.org/problem?id=1273
题目大意:
有一个水塘,一个大海,要把水塘里的水尽可能多的排到大海里。当然,要通过一些水渠,这些水渠有一定的容量限制。
问最多能有多少水能流到大海里。
解题思路:
最大流的入门题。看了一上午就做了出来,很简单其实。。。用的BFS和Ford_Fulkerson算法。网上资料很多,大概看看应该就理解了。网络流开始还是很是不难的。建图是关键,要学会一定的建图方法。。。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define N 210
#define MAX 1 << 25
int network[N][N];
bool visit[N];
int que[N], head, tail; //广搜队列
int pre[N]; //祖先(用于更新残余网络)
int flow[N]; //可行流量
int n, m;
int BFS() //增广路
{
head = tail = 0;
for(int i = 1; i <= m; ++i)
pre[i] = -1;
for(int i = 1; i <= m; ++i)
flow[i] = MAX;
memset(visit, false, sizeof(visit));
visit[1] = true;
que[tail++] = 1;
while(head < tail)
{
int cur = que[head++];
if(cur == m)
break;
for(int i = 2; i <= m; ++i)
{
if(!visit[i] && network[cur][i]) //增广路
{
visit[i] = true;
flow[i] = min(flow[cur], network[cur][i]);
pre[i] = cur;
que[tail++] = i;
}
}
}
if(!visit[m])
return -1;
else
return flow[m];
}
int Ford_Fulkerson()
{
int maxflow = 0, nowflow;
while((nowflow = BFS()) != -1)
{
maxflow += nowflow;
int temp = m, res;
while(temp != 1) //更新残余网络
{
res = pre[temp];
network[res][temp] -= nowflow;
network[temp][res] += nowflow;
temp = res;
}
}
return maxflow;
}
int main()
{
int start, end, water;
while(~scanf("%d%d", &n, &m))
{
memset(network, 0, sizeof(network));
for(int i = 0; i < n; ++i)
{
scanf("%d%d%d", &start, &end, &water); //重边叠加~。~
network[start][end] += water;
}
printf("%d\n", Ford_Fulkerson());
}
return 0;
}
SAP实现代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 210
#define MAX 1<<28
#define CLR(arr, what) memset(arr, what, sizeof(arr))
int maze[N][N];
int pre[N], cur[N];
int gap[N];
int dis[N];
int source, sink, nodenum;
int SAP(int s, int t, int n)
{
CLR(gap, 0); CLR(cur, 0); CLR(dis, 0);
int u = pre[s] = s, maxflow = 0, aug = MAX, v;
gap[0] = n;
while(dis[s] < n)
{
bool flag = false;
for(v = cur[u]; v <= n; ++v) //寻找允许弧
{
if(maze[u][v] > 0 && dis[u] == dis[v] + 1)
{
flag = true;
break;
}
}
if(flag) //找到允许弧
{
pre[v] = u;
cur[u] = v;
aug = min(aug, maze[u][v]);
u = v;
if(v == t) //找到完整增广路
{
maxflow += aug;
for(v = t; v != s; v = pre[v]) //更新残留网络
{
maze[pre[v]][v] -= aug; //正向边
maze[v][pre[v]] += aug; //反向边
}
aug = MAX, u = s; //重新从源点寻找
}
}
else //找不到允许弧
{
int mindis = n;
for(v = 1; v <= n; ++v) //重新标号
{
if(maze[u][v] && mindis > dis[v])
{
cur[u] = v;
mindis = dis[v];
}
}
if(--gap[dis[u]] == 0) //更新断层 + 判断是否断层(间隙优化)
break;
gap[dis[u] = mindis + 1]++; //更新断层
u = pre[u]; //当前弧优化
}
}
return maxflow;
}
int main()
{
int n, m;
int start, end, cost;
int answer;
while(~scanf("%d%d", &n, &m))
{
CLR(maze, 0);
source = 1, sink = m, nodenum = m;
for(int i = 0; i < n; ++i)
{
scanf("%d%d%d", &start, &end, &cost);
maze[start][end] += cost;
}
answer = SAP(source, sink, nodenum);
printf("%d\n", answer);
}
return 0;
}