題意：給出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;i0)
{
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]
