```cpp
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
#define MAX 0x33ffffffffffffff
using namespace std;
struct NODE{
int val,id;
NODE(int a=0,int b=0){
id=a;val=b;
}
};
struct DUI{
NODE dui[450000];
int dtop;
void init(){
dtop=0;
}
bool cmp(NODE x,NODE y){
return x.val>y.val;
}
void add(int x,int val){
dtop++;
dui[dtop]=NODE(x,val);
int zz=dtop;
while(zz>1){
if(cmp(dui[zz>>1],dui[zz])){
swap(dui[zz>>1],dui[zz]);
zz>>=1;
}
else break;
}
}
NODE push(){
NODE RE=dui[1];
dui[1]=dui[dtop--];
int zz=1;
while((zz<<1)<=dtop){
int zzz;
if((zz<<1|1)<=dtop&&cmp(dui[zz<<1|1],dui[zz<<1]))zzz=zz<<1|1;
else zzz=zz<<1;
if(cmp(dui[zzz],dui[zz])){
swap(dui[zzz],dui[zz]);
zz=zzz;
}
else break;
}
return RE;
}
}dui;
int fir[25000],nxt[450000],to[450000],qp[450000],cost[450000],top=1;
int n,m,s,t;
int h[25000],val[25000],pd[45000];
int in[25000];
int dl[25000],l,r;
int ans;
void add(int x,int y,int z,int C){
top++;nxt[top]=fir[x];fir[x]=top;to[top]=y;qp[top]=z;cost[top]=C;
}
void bfs(){
for(int i=1;i<=n;i++)h[i]=INF;
h[t]=0;
l=1,r=0;
dl[++r]=t;
while(l<=r){
int x=dl[l++];
for(int i=fir[x];i;i=nxt[i]){
if(qp[i^1]&&h[to[i]]>h[x]+1){
h[to[i]]=h[x]+1;
dl[++r]=to[i];
}
}
}
}
void push(int x){
while(val[x]){
int ER=-1;
for(int i=fir[x];i;i=nxt[i]){
if(qp[i]&&h[x]==h[to[i]]+1){
if(ER==-1||to[ER]==s)ER=i;
else if(to[i]!=s)ER=(cost[ER]>cost[i])? i:ER;
}
}
if(ER==-1)break;
int ll=min(qp[ER],val[x]);
val[x]-=ll;val[to[ER]]+=ll;
qp[ER]-=ll;qp[ER^1]+=ll;
ans+=cost[ER]*ll;
if(to[ER]!=s&&to[ER]!=t&&!in[to[ER]]){
dui.add(to[ER],h[to[ER]]);
in[to[ER]]=1;
}
}
}
void relabel(int x){
h[x]=INF;
for(int i=fir[x];i;i=nxt[i]){
if(qp[i]&&h[x]>h[to[i]]+1){
h[x]=h[to[i]]+1;
}
}
}
void HLPP(){
bfs();
if(h[s]==INF){
return ;
}
h[s]=2*n;
memset(pd,0,sizeof(pd));
for(int i=1;i<=n;i++){
if(h[i]<INF)pd[h[i]]++;
}
for(int i=fir[s];i;i=nxt[i]){
if(qp[i]){
val[to[i]]+=qp[i];
val[s]-=qp[i];
ans+=cost[i]*qp[i];
swap(qp[i],qp[i^1]);
if(to[i]!=t&&!in[to[i]]){
dui.add(to[i],h[to[i]]);
in[to[i]]=1;
}
}
}
while(dui.dtop){
int x=dui.push().id;
in[x]=0;
push(x);
if(val[x]){
if(!--pd[h[x]]){
for(int i=1;i<=n;i++){
if(i!=s&&i!=t&&h[i]>h[x]&&h[i]<n+1){
h[i]=n+1;
}
}
}
relabel(x);pd[h[x]]++;
dui.add(x,h[x]);in[x]=1;
}
}
}
signed main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,z,Z;
scanf("%lld%lld%lld%lld",&x,&y,&z,&Z);
add(x,y,z,Z);add(y,x,0,-Z);
}
HLPP();
cout<<val[t]<<" "<<ans<<endl;
}
```
by w20230071_QwQ @ 2022-05-18 19:38:21
WA了最后4个点
by w20230071_QwQ @ 2022-05-18 19:39:44
问题应该是跑完之后网络里会有若干负环,
希望能通过修改让其不再产生;
或在不用传统网络流的情况下最后统一消除
by w20230071_QwQ @ 2022-05-18 19:43:22