2018年模板大集合！！！！没有一个优秀的模板就是等着被摩擦[网络流]
dinic网络流裸板子(edn清0，p重置为-1，sp与tp为全局变量)：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+7;
const ll Ni=4040;
const ll INF=1e9;
const ll MAX=1<<26;
struct Edge{
ll u,v,c,next;
}edge[20*Ni];
ll n,m,edn,p[Ni],d[Ni],sp,tp;
void addedge(ll u,ll v,ll c){
edge[edn].u=u;edge[edn].v=v;edge[edn].c=c;
edge[edn].next=p[u];p[u]=edn++;
edge[edn].u=v;edge[edn].v=u;edge[edn].c=0;
edge[edn].next=p[v];p[v]=edn++;
}
ll bfs(){
queue<ll>q;
memset(d,-1,sizeof(d));
d[sp]=0;q.push(sp);
while(!q.empty()){
ll cur=q.front();q.pop();
for(ll i=p[cur];i!=-1;i=edge[i].next){
ll u=edge[i].v;
if(d[u]==-1&&edge[i].c>0){
d[u]=d[cur]+1;q.push(u);
}
}
}
return d[tp]!=-1;
}
ll dfs(ll a,ll b){
ll r=0;
if(a==tp)return b;
for(ll i=p[a];i!=-1&&r<b;i=edge[i].next){
ll u=edge[i].v;
if(edge[i].c>0&&d[u]==d[a]+1){
ll x=min(edge[i].c,b-r);
x=dfs(u,x);
r+=x;
edge[i].c-=x;edge[i^1].c+=x;
}
}
if(!r)d[a]=-2;
return r;
}
ll dinic(ll sp,ll tp){
ll total=0,t;
while(bfs()){
while(t=dfs(sp,MAX))
total+=t;
}
return total;
}
ll list1[maxn],in1[maxn];
ll C[maxn];
int main(){
//freopen("in.txt","r",stdin);
ll i,v,j,k,u,b,t1,t2,t3,T,num;
ll upper,lower,X,Y;
scanf("%lld %lld %lld %lld",&n,&m,&sp,&tp);
edn=0;memset(p,-1,sizeof(p));
//X=n+1;Y=n+2;
ll tot1=0;
for(i=1;i<=m;i++){
scanf("%lld %lld %lld",&t1,&t2,&t3);
addedge(t1,t2,t3);
}
cout <<dinic(sp,tp) <<endl;
return 0;
}
据说会快一下的另外一个板子ISAP网络流：
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef struct {ll v,next,val;} edge;
const int MAXN=20010;
const int MAXM=500010;
edge e[MAXM];
ll p[MAXN],eid;
inline void init(){memset(p,-1,sizeof(p));eid=0;}
inline void insert1(ll from,ll to,ll val){//有向
e[eid].v=to;e[eid].val=val;
e[eid].next=p[from];
p[from]=eid++;
swap(from,to);
e[eid].v=to;e[eid].val=0;//如果是无方，这里改为val
e[eid].next=p[from];
p[from]=eid++;
}
ll n,m;//n为点数 m为边数
ll h[MAXN];
ll gap[MAXN];
ll source,sink;
inline ll dfs(ll pos,ll cost){
if (pos==sink) return cost;
ll j,minh=n-1;
ll lv=cost,d;
for (j=p[pos];j!=-1;j=e[j].next){
ll v=e[j].v,val=e[j].val;
if(val>0){
if (h[v]+1==h[pos]){
if (lv<e[j].val) d=lv;
else d=e[j].val;
d=dfs(v,d);
e[j].val-=d;
e[j^1].val+=d;
lv-=d;
if (h[source]>=n) return cost-lv;
if (lv==0) break;
}
if (h[v]<minh) minh=h[v];
}
}
if (lv==cost){
--gap[h[pos]];
if (gap[h[pos]]==0) h[source]=n;
h[pos]=minh+1;
++gap[h[pos]];
}
return cost-lv;
}
ll isap(ll st,ll ed){
source=st;sink=ed;
ll ret=0;
memset(gap,0,sizeof(gap));
memset(h,0,sizeof(h));
gap[st]=n;
while (h[st]<n){
ret+=dfs(st,INT_MAX);
}
return ret;
}
int main(){
ll sp,tp;
//freopen("in.txt","r",stdin);
cin >> n >>m>> sp>> tp;
init();
for(ll i=0;i<m;i++){
ll u,v,c;
scanf("%lld%lld%lld",&u,&v,&c);
insert1(u,v,c);
}
printf("%lld\n",isap(sp,tp)); //这里是从1走到n
return 0;
}
无源汇上下界网络流判是否可行:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+7;
const ll Ni=4040;
const ll INF=1e9;
const ll MAX=1<<26;
struct Edge{
ll u,v,c,next,C;
}edge[20*Ni];
ll n,m,edn,p[Ni],d[Ni],sp,tp;
void addedge(ll u,ll v,ll c){
edge[edn].u=u;edge[edn].v=v;edge[edn].c=c;
edge[edn].C=c;
edge[edn].next=p[u];p[u]=edn++;
edge[edn].u=v;edge[edn].v=u;edge[edn].c=0;
edge[edn].C=c;
edge[edn].next=p[v];p[v]=edn++;
}
ll bfs(){
queue<ll>q;
memset(d,-1,sizeof(d));
d[sp]=0;q.push(sp);
while(!q.empty()){
ll cur=q.front();q.pop();
for(ll i=p[cur];i!=-1;i=edge[i].next){
ll u=edge[i].v;
if(d[u]==-1&&edge[i].c>0){
d[u]=d[cur]+1;q.push(u);
}
}
}
return d[tp]!=-1;
}
ll dfs(ll a,ll b){
ll r=0;
if(a==tp)return b;
for(ll i=p[a];i!=-1&&r<b;i=edge[i].next){
ll u=edge[i].v;
if(edge[i].c>0&&d[u]==d[a]+1){
ll x=min(edge[i].c,b-r);
x=dfs(u,x);
r+=x;
edge[i].c-=x;edge[i^1].c+=x;
}
}
if(!r)d[a]=-2;
return r;
}
ll dinic(ll sp,ll tp){
ll total=0,t;
while(bfs()){
while(t=dfs(sp,MAX))
total+=t;
}
return total;
}
ll list1[maxn],in1[maxn];
ll C[maxn];
ll M[maxn];
int main(){
//freopen("in.txt","r",stdin);
ll i,v,j,k,u,b,t1,t2,t3,num;
ll upper,lower,X,Y;
ll S,T;
scanf("%lld %lld",&n,&m);
edn=0;memset(p,-1,sizeof(p));
S=sp;T=tp;
ll tot1=0;
X=n+1;Y=n+2;
ll sum1=0;
for(i=1;i<=m;i++){
scanf("%lld %lld %lld %lld",&t1,&t2,&lower,&upper);
list1[++tot1]=edn;
C[tot1]=lower;
addedge(t1,t2,upper-lower);
M[t2]+=lower;M[t1]-=lower; //这里需要记录每个点是加还是减
}
for(int i=1;i<=n;++i)
if(M[i]>=0){
sum1+=M[i];
addedge(X,i,M[i]);
}else addedge(i,Y,-M[i]);
//addedge(tp,sp,INF);
sp=X;tp=Y;
int res=dinic(sp,tp);
if(res!=sum1){
printf("NO\n");return 0;
}
printf("YES\n");
for(i=1;i<=tot1;i++) //输出每条边的容量
cout << C[i]+edge[list1[i]].C-edge[list1[i]].c <<endl;
return 0;
}
有源汇上下界网络流，
按照这样建立图片建立一个新的x与y，u连到y为下限，x连到v为下限，然后跑一个x到y的最大流，判断所有必须流是否满。
这里第限制为[2,6],[3,4],[3,7]
板子：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+7;
const ll Ni=4040;
const ll INF=1e9;
const ll MAX=1<<26;
struct Edge{
ll u,v,c,next;
}edge[20*Ni];
ll n,m,edn,p[Ni],d[Ni],sp,tp;
void addedge(ll u,ll v,ll c){
edge[edn].u=u;edge[edn].v=v;edge[edn].c=c;
edge[edn].next=p[u];p[u]=edn++;
edge[edn].u=v;edge[edn].v=u;edge[edn].c=0;
edge[edn].next=p[v];p[v]=edn++;
}
ll bfs(){
queue<ll>q;
memset(d,-1,sizeof(d));
d[sp]=0;q.push(sp);
while(!q.empty()){
ll cur=q.front();q.pop();
for(ll i=p[cur];i!=-1;i=edge[i].next){
ll u=edge[i].v;
if(d[u]==-1&&edge[i].c>0){
d[u]=d[cur]+1;q.push(u);
}
}
}
return d[tp]!=-1;
}
ll dfs(ll a,ll b){
ll r=0;
if(a==tp)return b;
for(ll i=p[a];i!=-1&&r<b;i=edge[i].next){
ll u=edge[i].v;
if(edge[i].c>0&&d[u]==d[a]+1){
ll x=min(edge[i].c,b-r);
x=dfs(u,x);
r+=x;
edge[i].c-=x;edge[i^1].c+=x;
}
}
if(!r)d[a]=-2;
return r;
}
ll dinic(ll sp,ll tp){
ll total=0,t;
while(bfs()){
while(t=dfs(sp,MAX))
total+=t;
}
return total;
}
ll list1[maxn],in1[maxn];
ll C[maxn];
ll M[maxn];
int main(){
//freopen("in.txt","r",stdin);
ll i,v,j,k,u,b,t1,t2,t3,num;
ll upper,lower,X,Y;
ll S,T;
scanf("%lld %lld %lld %lld",&n,&m,&sp,&tp);
edn=0;memset(p,-1,sizeof(p));
S=sp;T=tp;
ll tot1=0;
X=n+1;Y=n+2;
for(i=1;i<=m;i++){
scanf("%lld %lld %lld %lld",&t1,&t2,&lower,&upper);
addedge(t1,t2,upper-lower);
M[t2]+=lower;M[t1]-=lower; //这里需要记录每个点是加还是减
}
for(int i=1;i<=n;++i)
if(M[i]>=0)addedge(X,i,M[i]);
else addedge(i,Y,-M[i]);
addedge(tp,sp,INF);
sp=X;tp=Y;
dinic(sp,tp);
for(int i=p[X];i!=-1;i=edge[i].next)if(edge[i].c){ //这一步判断是否有可行流
printf("please go home to sleep\n");return 0;
}
int ans=0;
//注意这里改变的是之前的sp和tp
p[T]=edge[p[T]].next;p[S]=edge[p[S]].next;
sp=S;tp=T;
ans+=dinic(S,T);
ans+=edge[edn-1].c;
printf("%d\n",ans);
return 0;
}
有源汇上下界最小流，~不会，拿了别人的板子：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=50200;
struct node{
ll t,cap,flow,next; //cap容量，flow流量
}e[N*12];
int head[N],vis[N],cnt;
void add(int u,int v,ll cap) //u->v容量为cap{
e[cnt]=node{v,cap,0,head[u]};
head[u]=cnt++;
e[cnt]=node{u,0,0,head[v]}; //容量为0的反向边
head[v]=cnt++;
}
int d[N]; //bfs深度
bool bfs(int s,int t) //O(n+m){
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];~i;i=e[i].next){
int v=e[i].t;
if(d[v]==0&&e[i].cap-e[i].flow>0){
d[v]=d[u]+1;
q.push(v);
}
}
}
return d[t]>0; //存在增广路
}
ll dfs(int s,int t,ll minedge){
if(s==t)return minedge;
ll flow=0; //从当前s点流出的流量
for(int &i=vis[s];~i;i=e[i].next){
int v=e[i].t;
if(d[v]==d[s]+1&&e[i].cap-e[i].flow>0){ //层次关系&&有剩余流量
ll temp=dfs(v,t,min(minedge-flow,e[i].cap-e[i].flow));
e[i].flow+=temp; //流量增加
e[i^1].flow-=temp; //反向边流量减少
flow+=temp; //flow已分配的流量
if(flow==minedge)return flow; //已达到祖先的最大流，无法再大，剪枝
}
}
if(flow==0)d[s]=0; //此点已无流，标记掉
return flow;
}
ll dinic(int s,int t){ //一定要建立反向边cap=0
ll maxflow=0;
while(bfs(s,t)) //有增广路
{
memcpy(vis,head,sizeof(head));
maxflow+=dfs(s,t,INF);
}
return maxflow;
}
ll bout[N],low[N*10];
int main(){
int n,m,s,t,u,v;
ll b,c;
while(cin>>n>>m>>s>>t){
memset(head,-1,sizeof(head));
cnt=0;
memset(bout,0,sizeof(bout));
for(int i=0;i<m;i++){
scanf("%d%d%lld%lld",&u,&v,&b,&c);
add(u,v,c-b);
bout[u]+=b;
bout[v]-=b;
low[i]=b;
}
int ss=n+1,tt=n+2;
ll sum=0;
for(int i=1;i<=n;i++){
if(bout[i]>0)sum+=bout[i],add(i,tt,bout[i]);
if(bout[i]<0)add(ss,i,-bout[i]);
}
ll res=dinic(ss,tt);
add(t,s,INF);
res+=dinic(ss,tt);
if(sum==res)printf("%lld\n",e[cnt-2].flow);
else printf("please go home to sleep\n");
}
}