?
题意：给出n个河流，m个点，以及每个河流的流量，求从1到m点的最大流量。 思路：最裸的网络流题目 意思就是求从源点到汇点的最大流。
第一道网络流，一边看着书上的介绍，一边敲下代码:
用的是网络流算法ford-fulkerson
题目数据量小，邻接表和邻接矩阵都可以过
?
代码：
?
#include
//最大流 入门
#include
#include
#include
#include
#include
#include
using namespace std; const int maxn = 1101; const int inf=0x3f3f3f3f; struct edge {int to,cap,rev;}; vector
G[maxn]; //图的邻接表表示 bool used[maxn]; //访问标记 void add_edge(int from,int to,int cap) { G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size()-1}); } int dfs(int v,int t,int f) { if(v==t) return f; used[v]=true; for(int i=0;i
0) { int d=dfs(e.to,t,min(f,e.cap)); if(d>0) { e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; for(;;) { memset(used,0,sizeof(used)); int f=dfs(s,t,inf); if(f==0) return flow; flow+=f; } } int main() { int n,m,too,capp,revv; while(~scanf(%d%d,&n,&m)) { memset(G,0,sizeof(G)); for(int i=0;i
用邻接矩阵BFS实现：
?
?
#include
#include
#include
#include
#include
using namespace std; const int N = 300; const int MAX = 0x3f3f3f3f; int map[N][N]; int flow[N][N]; int a[N],p[N]; int Ford_fulkerson(int s,int t) { queue
qq; memset(flow,0,sizeof(flow)); int f=0,u,v; while(1) { memset(a,0,sizeof(a)); a[s]=MAX; qq.push(s); while(!qq.empty()) { u=qq.front();qq.pop(); for(v=1;v<=t;v++) { if(!a[v]&&map[u][v]>flow[u][v])//找到新结点v { p[v]=u;qq.push(v);//记录v的父亲，并加入FIFO队列 a[v]=a[u]
?