```cpp
```cpp
```/
by Qiuly @ 2019-03-22 20:55:23
```
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int n, m, s, t;
namespace header
{
const int N=400002;
int head[N];
struct node
{
int to, nxt, wei, cst;
} edge[N];
int cnt=1;
void add_edge(int f, int t, int w, int c)
{
cnt++;
edge[cnt].to=t;
edge[cnt].nxt=head[f];
edge[cnt].wei=w;
edge[cnt].cst=c;
head[f]=cnt;
return;
}
int dist[N];
bool vis[N];
bool spfa()
{
std::memset(dist, 0x3f, sizeof(dist));
std::memset(vis, 0x00, sizeof(vis));
std::queue<int> q;
q.push(s), dist[s]=0, vis[s]=true;
while (!q.empty())
{
int f=q.front();
q.pop();
vis[f]=false;
for (int i=head[f]; i!=-1; i=edge[i].nxt)
{
if (!edge[i].wei)
continue;
int to=edge[i].to;
if (dist[to]>dist[f]+edge[i].wei*edge[i].cst)
{
dist[to]=dist[f]+edge[i].wei*edge[i].cst;
if (!vis[to])
q.push(to), vis[to]=true;
}
}
}
return dist[t]!=0x3f3f3f3f;
}
int maxflow=0, mincost=0;
int dfs(int i, int minf)
{
//printf("in dfs(%d, %d)\n", i, minf);
if (i==t)
{
maxflow+=minf;
//printf("out of dfs, return %d\n", minf);
return minf;
}
int u=0;
for (int j=head[i]; j!=-1; j=edge[j].nxt)
{
int to=edge[j].to;
if (edge[j].wei&&dist[to]==dist[i]+edge[i].wei*edge[i].cst)
{
int f=dfs(to, std::min(minf-u, edge[j].wei));
mincost+=edge[i].cst*f;
u+=f;
edge[j].wei-=f;
edge[j^1].wei+=f;
if (minf==u)
break;
}
}
//printf("out of dfs, return %d\n", u);
return u;
}
}
using namespace header;
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i=1; i<=n; ++i)
head[i]=-1;
for (int i=1; i<=m; ++i)
{
int x, y, w, f;
scanf("%d%d%d%d", &x, &y, &w, &f);
add_edge(x, y, w, f);
add_edge(y, x, 0, -f);
}
while (spfa())
dfs(s, 0x3f3f3f3f);
printf("%d %d\n", maxflow, mincost);
return 0;
}
```
by 樱初音斗橡皮 @ 2019-03-22 20:55:30
@[樱初音斗橡皮](/space/show?uid=66287)
可以复制一下上面的格式
by Qiuly @ 2019-03-22 20:55:45
终于发了
by 樱初音斗橡皮 @ 2019-03-22 20:55:50
My Code:
```cpp
// luogu-judger-enable-o2
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=5e3+2;
const int inf=1e9+9;
template <typename _Tp> inline void IN(_Tp&x){
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
if(flag)x=-x;
}
int maxflow,cost;
int n,m,s,t,tot(1),head[N],vis[N],dist[N];
struct Edge{int nxt,to,val,cot;}G[N<<8];
struct Pre{int last,edge;}pre[N];
inline void add(int u,int v,int val,int cot){
G[++tot].nxt=head[u],G[tot].to=v,G[tot].val=val,G[tot].cot=cot,head[u]=tot;
G[++tot].nxt=head[v],G[tot].to=u,G[tot].val=0,G[tot].cot=-cot,head[v]=tot;
}
inline bool Spfa(){
memset(pre,0,sizeof(pre));
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
std::queue<int> q;
q.push(s),vis[s]=1,dist[s]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=G[i].nxt){
int v=G[i].to;
if(G[i].val>0&&dist[v]>dist[u]+G[i].cot){
dist[v]=dist[u]+G[i].cot;
pre[v].last=u,pre[v].edge=i;
if(!vis[v]){q.push(v),vis[v]=1;}
}
}vis[u]=0;
}return dist[t]!=0x3f3f3f3f;
}
inline int EK(){
maxflow=0;
cost=0;
int min_flow;
while(Spfa()){
min_flow=inf;
for(int i=t;i!=s;i=pre[i].last)
min_flow=min(min_flow,G[pre[i].edge].val);
for(int i=t;i!=s;i=pre[i].last){
G[pre[i].edge].val-=min_flow;
G[pre[i].edge^1].val+=min_flow;
}
maxflow+=min_flow;
cost+=min_flow*dist[t];
}return maxflow;
}
int main(){
IN(n),IN(m),IN(s),IN(t);
for(int i=1;i<=m;++i){
int u,v,val,cot;
IN(u),IN(v),IN(val),IN(cot);
add(u,v,val,cot);
}
printf("%d ",EK());
printf("%d",cost);
return 0;
}
```
by Qiuly @ 2019-03-22 20:56:03
@[樱初音斗橡皮](/space/show?uid=66287) 您不打EK_Spfa费用流吗QwQ
by Qiuly @ 2019-03-22 20:57:12
@[Qiuly](/space/show?uid=113190) 我要dinic
by 樱初音斗橡皮 @ 2019-03-22 20:57:45
```cpp
dist[to]==dist[i]+edge[i].wei*edge[i].cst)
```
这句很诡异诶，
by Qiuly @ 2019-03-22 21:00:12
@[樱初音斗橡皮](/space/show?uid=66287) 并不是必须要是最短路的遍才能转移，你可以加个dep，然后想正常的dinic那样判断
by Qiuly @ 2019-03-22 21:01:03
@[Qiuly](/space/show?uid=113190) 改成edge的wei仍然是TLE
by 樱初音斗橡皮 @ 2019-03-22 21:01:09