//lg p3381
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N= (int)5e3+3;
const int M =(int)5e4+4;
const ll INF = 0x3f3f3f3f;
int cur[N];
ll dis[N];
bool vis[N];
bool inq[N];
int edgeid=1;
int head[N];
struct edge {int v,cost,nxt;ll w;} e[2*M];
void addedge(int u,int v,int w,int cost)
{
edgeid++;
e[edgeid].v=v;
e[edgeid].cost=cost;
e[edgeid].w=w;
e[edgeid].nxt=head[u];
head[u]=edgeid;
}
ll mxflow,ans;
int n,m,st,ed;
deque<int> q;
bool Spfa()
{
memset(dis,INF,sizeof(dis));
memset(inq,0,sizeof(inq));
q.push_front(ed);
dis[ed]=0;
inq[ed]=1;
while(!q.empty())
{
int u=q.front();
q.pop_front();
inq[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>dis[u]-e[i].cost && e[i^1].w)
{
dis[v]=dis[u]-e[i].cost;
if(!inq[v])
{
if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
else q.push_back(v);
inq[v]=1;
}
}
}
}
return (dis[st]<=0x3f3f3f3f);
}
ll Dfs(int u,ll rst)
{
vis[u]=1;
if(u==ed || !rst) return rst;
ll sum=0;
for(int i=cur[u];i;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].v;
ll f;
if(dis[v]==dis[u]-e[i].cost && e[i].w && !vis[v]
&&(f=Dfs(v,min(rst,e[i].w))))
{
sum+=f;
rst-=f;
e[i].w-=f;
e[i^1].w+=f;
if(!rst) break;
}
}
return sum;
}
void Zkw()
{
while(Spfa())
{
do
{
for(int i=1;i<=n;i++) cur[i]=head[i];
memset(vis,0,sizeof(vis));
ll temp=Dfs(st,INF);
ans+=dis[st]*temp;
mxflow+=temp;
}while(vis[ed]);
}
}
int main()
{
cin>>n>>m>>st>>ed;
for(int i=1;i<=m;i++)
{
int u,v;
ll w,cost;
scanf("%d%d%lld%lld",&u,&v,&w,&cost);
addedge(u,v,w,cost);
addedge(v,u,0,-cost);
}
Zkw();
cout<<mxflow<<" "<<ans;
return 0;
}
标签:edgeid,int,ed,inq,板子,cost,Dinic,zkw,dis
From: https://www.cnblogs.com/yeyou26/p/18008996