我的作业部落有学习资料
Dinic 模板
#define rg register
#define _ 10001
#define INF 2147483647
#define min(x,y) (x)<(y)?(x):(y)
using namespace std;
int n,m,s,t,record[_],num_of_edges=-,cur[_],team[],depth[_];
struct pp
{
int next,to,w;
}edge[(_<<)+(_<<)];
inline int read()
{
rg int save=,w=;rg char q=getchar();
while(q<''||q>''){if(q=='-')w=-;q=getchar();}
while(q>=''&&q<='')save=(save<<)+(save<<)+q-'',q=getchar();
return save*w;
}
inline void add(rg int from,rg int to,rg int ww)
{
edge[++num_of_edges]=(pp){record[from],to,ww};
record[from]=num_of_edges;
}
inline bool bfs()
{
rg int head=,tail=;
for(rg int i=;i<=n;++i)depth[i]=;//depth[]初值为-1,免得返回出发点
depth[s]=;
team[]=s;
do
{
head++;
rg int u=team[head];
for(rg int j=record[u];j!=-;j=edge[j].next)
{
rg int to=edge[j].to;
if((!depth[to])&&(edge[j].w>))
{
depth[to]=depth[u]+;
team[++tail]=to;
if(to==t)return ;
}
}
}while(head<tail);
return ;
}
int dfs(rg int u,rg int flow)//找到每条路上的最小残余流量,因此需在回溯时更新每条边的流量
{
if(u==t)return flow;
for(rg int &j=cur[u]/*当前弧优化*/;j!=-;j=edge[j].next)
{
rg int to=edge[j].to;
if(depth[to]==depth[u]+&&(edge[j].w>))
{
rg int D=dfs(to,min(flow,edge[j].w));//到终点的过程中一直在取min
if(D>)
{
edge[j].w-=D,edge[j^].w+=D;
return D;//每次只找一条可流通路满上(这里就不管现实中物理的联通器原理了)
} }
}
return ;
}
inline int Dinic()
{
rg int i,j,ans=;
while(bfs())
{
for(i=;i<=n;++i)cur[i]=record[i];
while(int now=dfs(s,INF))ans+=now;
}
return ans;
}
int main()
{
n=read(),m=read(),s=read(),t=read();
rg int i,j;
for(i=;i<=n;++i)record[i]=-;
for(i=;i<=m;++i)
{
rg int x=read(),y=read(),ww=read();
add(x,y,ww),add(y,x,);
}
printf("%d\n",Dinic());
return ;
}
最小费用最大流:
#define rg register
#define _ 5001
#define __ 50001
#define INF 2147483647
using namespace std;
int n,m,s,t,record[_],num_of_edges=,pre[_],res_flow,res_cost,dis[_],team[__<<];//以后num_of_edges都赋为 1 !!!
bool exist[_];
struct pp
{
int next,to,w,cost;
}edge[__<<];
inline int read()
{
rg int save=,w=;rg char q=getchar();
while(q<''||q>''){if(q=='-')w=-;q=getchar();}
while(q>=''&&q<='')save=(save<<)+(save<<)+q-'',q=getchar();
return w*save;
}
inline void add(rg int from,rg int to,rg int ww,rg int f)
{
edge[++num_of_edges]=(pp){record[from],to,ww,f};
record[from]=num_of_edges;
}
inline bool SPFA()
{
rg int head=,tail=;
for(rg int i=;i<=n;++i)exist[i]=,dis[i]=INF;
dis[s]=;
team[]=s;
do
{
head++;
rg int i=team[head];
exist[i]=;
for(rg int j=record[i];j;j=edge[j].next)
{
rg int to=edge[j].to;
if(edge[j].w>&&dis[to]>dis[i]+edge[j].cost)
{
dis[to]=dis[i]+edge[j].cost;
pre[to]=j;
if(!exist[to])team[++tail]=to,exist[to]=;
}
}
}while(head<tail);
return dis[t]!=INF;
}
inline void doit()
{
while(SPFA())
{
rg int flow=INF;
for(rg int i=pre[t];i;i=pre[edge[i^].to])
flow=min(flow,edge[i].w);
res_flow+=flow;
res_cost+=dis[t]*flow;
for(rg int i=pre[t];i;i=pre[edge[i^].to])
edge[i].w-=flow,edge[i^].w+=flow;
}
printf("%d %d\n",res_flow,res_cost);
}
int main()
{
n=read(),m=read(),s=read(),t=read();
rg int i,j;
for(i=;i<=m;++i)
{
rg int u=read(),v=read(),w=read(),f=read();
add(u,v,w,f),add(v,u,,-f);
}
doit();//实在不想用那个MCMF()
return ;
}