网络流入门-POJ1459PowerNetwork-Dinic模板
(我有什么错误或者你有什么意见，欢迎留言或私聊！谢谢！)
(Ps:以前听说过网络流，想着以后再学，这次中南多校赛也碰到有关网络流的题目，想着这两天试着学学这个吧~~
这是本人网络流入门第二题，不知道怎么解释，
给大家推荐几个博客方便大家入门网络流：
看之前大家可以去百度一下网络流入门术语，这对新手入门网络流会有一些帮助）
题意：
用人话解释：
1. 给你 n 个点，m个边，num1个发电站，num2个用户；
2. 每条边有一个负载量，求用户收到的最大用电量；
3. 显而易见，是网络流中最大流的裸题，只是需要一个简单的处理；
4. 虽然每个发电站都是一个源点，每个用户都是一个汇点；但是你可以设置一个终极源点和终极汇点；
5. 意思是：终极源点0向每个发电站连一条边，权值为发电站的发电量；每个用户向终极汇点连一条边，权值为用户的限值量；当然还要建反向边；
6. 如此，题目便简化为求：点0到点n+1的最大流问题，Dinic板子水过，不过这板子应该还能优化。
思路：
1. 解题思路就在上面。
2. 说实话，关于算法本身我还说不出什么来，毕竟刚刚入门，（可能还没入门）对很多大神的解释还是一知半解，也就只能套板子写裸题了。
3. 关于网络流出了Dinic算法还有一些算法如：FF算法，EK算法，E’K’算法，预流推进算法，SAP算法；
4. 目前准备把每种算法的板子都准备好，板子来源就是从各个大佬博客搜刮！
5. 搜刮板子的同时，试着理解算法到底优化在哪里，强在哪里，为什么要那样处理；
6. 先从代码理解算法，然后试着搞懂算法的意思，各种专业术语也一定要理解；首先会写板子题，再试着写有一点难的题；
7. 听说网络流相关一些题目，难就难在如何建图，能建图就好解决了。看来如果不真正的理解网络流，只拘泥于板子题，实则啥都不会！
题目链接：
AC代码：
1266ms
#include<bits/stdc++.h> #define test printf("***\n") #define mm1(a) memset((a),-1,sizeof((a))) #define mm0(a) memset((a),0,sizeof((a))) #define mmx(a) memset((a),0x3f,sizeof((a))) #define lowbit(x) (x)&(-(x)) #define iis std::ios::sync_with_stdio(false) using namespace std; typedef long long LL; typedef unsigned long long uLL; const int N = 10005; const int M = 4100005; const int X = 999983; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; const double eps = 1e-8; const int mod = 1e9 + 7; int n,m,tot,num1,num2; int d[N]; //<font color=black size=4>1</font> int head[N]; struct lp{ int to,w,nex; lp(){} lp(int a,int b,int c){to=a;w=b;nex=c;} }cw[N*10]; inline void add(int a,int b,int c){ cw[++tot]=lp(b,c,head[a]); head[a]=tot; } inline bool bfs(){ mm1(d); queue<int>Q; Q.push(0);d[0]=0; while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int i=head[u];i!=-1;i=cw[i].nex){ int v=cw[i].to; if(cw[i].w&&d[v]==-1){ d[v]=d[u]+1; Q.push(v); } } } return d[n+1]!=-1; } //dfs这块有很多优化的地方可以加速，但是我还不会 //有什么弧优化和多路增广等 inline int dfs(int x,int f){ if(x==n+1||f==0) return f; int use=0,w; for(int i=head[x];i!=-1;i=cw[i].nex){ int to=cw[i].to; if(d[to]==d[x]+1 && cw[i].w){ w=dfs(to,min(cw[i].w,f-use)); cw[i].w-=w,cw[i^1].w+=w; use+=w; if(use==f) return f; } } return use; } inline void init(){ tot=-1; mm1(head); } int main(){ #ifdef DEBUG freopen("D:in.in", "r", stdin); freopen("D:out.out", "w", stdout); #endif while(cin>>n>>num1>>num2>>m){ init(); int x,y,z,a,b;char o; for(int i=0;i<m;++i){ cin>>o>>x>>o>>y>>o>>z; add(x+1,y+1,z);add(y+1,x+1,0); } for(int i=0;i<num1;++i){ cin>>o>>a>>o>>b; add(0,a+1,b);add(a+1,0,0); } for(int i=0;i<num2;++i){ cin>>o>>a>>o>>b; add(a+1,n+1,b);add(n+1,a+1,0); } int ans=0; while(bfs()){ ans+=dfs(0,1e7); } printf("%d\n",ans ); } #ifdef DEBUG fclose(stdout); fclose(stdin); #endif return 0; }
View Code