这几天学网络流学到快吐血.. 先写最大流,下一篇写费用流. 网络流定义: 嗯..基本就是不知哪个大神看水管里水流啊流而发明的高妙算法,将一个问题构建成网络流模型,类比水流流动解决.(一般来说问题的最优解就对应网络流中最[大/小]流). 最大流: 让管道总流量最大,这个东西算法中高妙的地方在于反向边,可以不断增广而使复杂度降得很低,具体的东西网上一抓一大把,懒得打.. 最大流板子:(dinic算法,好写好用)
#pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; const int inf=INT_MAX; const int N=20010; int s,t,cnt=-1; int head[N],next[N*10],to[N*10],las[N*10],deep[N],cur[N]; bool bfs()//找残量网络建分层图(听上去很高端其实就是从源点开始bfs到的点一个"bfs序"..) { int now;queue<int>q; memset(deep,0,sizeof deep); deep[s]=1; q.push(s); while(!q.empty()) { now=q.front();q.pop(); for(int i=head[now];i!=-1;i=next[i]) { if(!deep[to[i]]&&las[i])deep[to[i]]=deep[now]+1,q.push(to[i]); } } return deep[t]; } int dfs(int pos,int flow)//增广 { if(pos==t)return flow; for(int &i=cur[pos];i!=-1;i=next[i])//一个叫当前弧优化的东西,降低常数,原理不太懂. { if(deep[to[i]]==deep[pos]+1&&las[i]) { int now=dfs(to[i],min(flow,las[i])); if(now) { las[i]-=now; las[i^1]+=now; return now; } } } return 0; } void add_edge(int u,int v,int w)//加边 { next[++cnt]=head[u]; las[cnt]=w;to[cnt]=v; head[u]=cnt; } inline void init() { memset(next,-1,sizeof next); memset(head,-1,sizeof head); return; } int main() { int n,m,u,v,w,ans=0,tmp; init(); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,0);//反向边 } while(bfs()) { for(int i=1;i<=n;i++)//每次重置当前弧优化的cur数组 cur[i]=head[i]; while(tmp=dfs(s,inf)) ans+=tmp; } printf("%d",ans); return 0; }