P3381最小费用最大流求助EK+spfa73分

rt```cpp using namespace std; #include<bits/stdc++.h> #define ll long long ll n,m,s,t; ll u,v,w,c;const ll N=5e3+7; ll flag[N][N]; ll ans=0; ll kk=0;ll kkk=0; struct edge{ ll to,nxt,val,cost; }ed[N<<2];ll head[N];ll cntt=1; ll dis[N]; ll pre[N];ll vis[N]; void add_t(ll u,ll v,ll w,ll c){ ed[++cntt].nxt=head[u]; ed[cntt].to=v;ed[cntt].val=w;head[u]=cntt; ed[cntt].cost=c; ed[++cntt].nxt=head[v]; ed[cntt].to=u;ed[cntt].val=0; head[v]=cntt; ed[cntt].cost=-c; // cout<<"Sd/f"; } ll ds[N]; ll bfs(){ // cout<<"Df";

// cout<<"Sdf"; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); memset(ds,0x3f,sizeof(ds)); queue q; q.push(s); vis[s]=1; ds[s]=0; dis[s]=0x3f3f3f3f3f3f3f3f; while(!q.empty()){ // cout<<"sf"; ll x=q.front(); q.pop(); vis[x]=0; for(ll i=head[x];i;i=ed[i].nxt){ if(ed[i].val==0) continue; ll v=ed[i].to; if(ds[v]>ds[x]+ed[i].cost){ ds[v]=ds[x]+ed[i].cost; dis[v]=min(dis[x],ed[i].val);

		pre[v]=i;
		if(!vis[v]){
			q.push(v);
			vis[v]=1;
		}
		

// cout<<"sdf"; }

	}

// cout<<"SDfsdf"; } return dis[t]>0;

} void upd(){ ll x=t; while(x!=s){ // cout<<"dsf"; int v=pre[x]; ed[v].val-=dis[t]; ed[v^1].val+=dis[t]; x=ed[v^1].to; // cout<<x<<'-'; // cout<<"SDF";

}

// cout<<"DFS"; kk+=dis[t];//cout<<"sdf"; kkk+=dis[t]*ds[t];

return;

} int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ cin>>u>>v>>w>>c;

	if(flag[u][v]==0){
		add_t(u,v,w,c);
		flag[u][v]=cntt;
	}else{
		ed[flag[u][v]-1].val+=w;
	}
}

while(bfs()!=0){
	upd();
}

cout<<kk<<' '<<kkk;

}