```cpp
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct edge{
int from,to;
long long flow,cost;
int rev,next;
};
edge Edge[50011];
int cnt=1,head[5011];
inline void add_edge(int from,int to,long long flow,long long cost)
{
Edge[cnt]=(edge){from,to,flow,cost,cnt+1,head[from]};
head[from]=cnt++;
Edge[cnt]=(edge){to,from,0,-cost,cnt-1,head[to]};
head[to]=cnt++;
}
long long n,m,mincost,maxflow;
long long flow[5011],dis[5011],pre[5011];
bool vst[5011];
bool spfa(int S,int T)
{
for (register int i=1;i<=n;i++)
{
vst[i]=false;
dis[i]=2147483647LL;
}
queue<int> q;
dis[S]=0;
vst[S]=true;
flow[S]=2147483647LL;
q.push(S);
while (!q.empty())
{
int f=q.front();
q.pop();
vst[f]=false;
for (register int i=head[f];i;i=Edge[i].next)
{
int to=Edge[i].to;
if (Edge[i].flow>0 && dis[to]>dis[f]+Edge[i].cost)
{
dis[to]=dis[f]+Edge[i].cost;
pre[to]=i;
flow[to]=min(flow[f],Edge[i].flow);
if (!vst[to])
{
q.push(to);
vst[to]=true;
}
}
}
}
return dis[T]!=2147483647LL;
}
inline void EK(int S,int T)
{
int nowflow=0;
maxflow=0,mincost=0;
while (spfa(S,T))
{
int now=T;
nowflow=flow[T];
while (now!=S)
{
Edge[pre[now]].flow-=nowflow;
Edge[Edge[pre[now]].rev].flow+=nowflow;
now=Edge[pre[now]].from;
}
mincost+=dis[T]*nowflow;
maxflow+=nowflow;
}
}
int main()
{
int S,T;
ios::sync_with_stdio(false);
cin>>n>>m>>S>>T;
for (register int i=1;i<=m;i++)
{
int f,t,fl,c;
cin>>f>>t>>fl>>c;
add_edge(f,t,fl,c);
}
EK(S,T);
cout<<maxflow<<' '<<mincost<<endl;
cout<<endl;
return 0;
}
```
我都开了long long了也不对
不知道为啥
by Jelly_Goat @ 2019-07-21 15:41:50
关于SPFA，它死了
by hxwht @ 2019-07-21 15:42:30
@[hxwht](/space/show?uid=154814)
关于SPFA，他A了（今年的某题卡住了dij）
by Jelly_Goat @ 2019-07-21 15:47:07
加个SLF优化一下SPFA应该能过
by Zofia @ 2019-07-21 15:48:49
@[杨林树♂](/space/show?uid=117068)
SLF是啥
by Jelly_Goat @ 2019-07-21 15:50:02
@[Jelly_Goat](/space/show?uid=122927) 双端队列优化
by ZORO @ 2019-07-21 16:23:55
@[hxwht](/space/show?uid=154814) 听说个句子就敢在讨论区胡说八道了？费用流的题你给我构造个卡SPFA的数据？请
by 一扶苏一 @ 2019-07-21 16:26:34
@[Jelly_Goat](/space/show?uid=122927) 楼上胡说八道，RE的是边表的大小开小了，双向边开2m
by 一扶苏一 @ 2019-07-21 16:27:41
楼上代码都不看就敢闭眼胡吹真是 nb 的很嗷
by 一扶苏一 @ 2019-07-21 16:30:11
@[一扶苏一](/space/show?uid=65363)
Thanks
~~没想到应该是二倍空间~~
%zay
by Jelly_Goat @ 2019-07-21 16:38:16