1Luogu 3376&POJ 1273 Drainage Ditches这两题是最大流，也就是最基本的网络流的最基本的题，初学者最好先写写这两题（我不会告诉你其实两题是一样的）题目大意如下：现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量其实你把这个池塘当做点，水渠当做边，就可以了，不过要注意两题在输入上有一些差别，洛谷的题有给源点和汇点，poj的题则没有，其实这不难，只要把洛谷3376的程序中s定义为1，t定义为m就可以了
2洛谷3376程序 代码长度1.4kB 耗时818ms，这里用的是后面的网络流中很重要的一个dinic算法，它的做法先bfs求出bfs序，当要找增广路（可以增加的路径时），先判断这条边终点的bfs序是否等于起点的bfs序+1，如果是的话，再增广，否则，找另一条边#include #include #include #include #include #include #include using namespace std;int n,m,s,t,u,v,w,e,dist[10005],x;queue q;struct aa{ int to,w,next;}edge[200005];//建边要用边表，要不然时间会爆int head[10005],flow,maxflow;bool add(int u,int to,int w){ edge[e].next=head[u]; edge[e].to=to; edge[e].w=w; head[u]=e++;}//边表的建边操作，大家应该很熟悉，这里就不讲了bool bfs(){ memset(dist,0,sizeof(dist));//初始化 dist[s]=1; q.push(s); while(q.empty()==0) { int k=q.front();q.pop(); for(int i=head[k];~i;i=edge[i].next) { if(edge[i].w && !dist[edge[i].to])dist[edge[i].to]=dist[k]+1,q.push(edge[i].to); } } return dist[t];//如果s和t不连通，则返回0}//求每个点的bfs序int dfs(int u,int flow){ if(u==t)return flow;//如果当前点=终点，终止循环 if(dist[u]>=dist[t])return 0;如果当前的的bfs序大于t的dfs序，则这不是一个合法的网络流，此时return 0 for(int i=head[u];~i;i=edge[i].next) { if(edge[i].w && dist[edge[i].to]==dist[u]+1 && (x=dfs(edge[i].to,min(edge[i].w,flow))))//如果这条边的权值>0 && 终点的bfs序大于起点的bfs序 && 这条边的终点能走到t，则执行 { edge[i].w-=x; edge[i^1].w+=x;//这步很重要，是所谓的加入后向边，防止这种策略错误，如果错误，还能原路走回来 return x; } } return 0;}int main(){ scanf('%d%d%d%d',&n,&m,&s,&t);//输入 memset(head,-1,sizeof(head));//初始化，这步很重要，我本来没加这步就wa了三个点 for(int i=1;i<=m;i++) { scanf('%d%d%d',&u,&v,&w);//输入 add(u,v,w); add(v,u,0); //加边，记住网络流中正向的边和反向的边都要加，正向的按输入的权值加边，反向的按权值为0加边，记住，反向的边一定要加 } while(bfs())//循环，当bfs（）的结果不为0时，进入循环 { while(x=dfs(s,1e9))//循环并且赋值，这个语句时将dfs(s,1e9)的值赋给x，并且进行判断，当x=0时跳出循环，否则，执行这个循环 { maxflow+=x;累加答案 } } printf('%d\n',maxflow);输出 return 0;}
