Wa了两个点,Re了三个点!!! 以下代码:
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+1000;
const int M=5e4+100;
const int INF=0x7f7f7f7f;
int a,b,c,d;
int end;
int src,des,ans,dis[N];
int m=1,adj[N],nxt[N],go[M],cap[M],cost[M];
bool vis[N],walk[N];
queue<int> que;
inline void addEdge(int u,int v,int f,int w){
nxt[++m]=adj[u],adj[u]=m,go[m]=v,cap[m]=f,cost[m]=w;
nxt[++m]=adj[v],adj[v]=m,go[m]=u,cap[m]=0,cost[m]=-w;
}
inline bool spaf(){
memset(dis,INF,sizeof(dis));
memset(walk,0,sizeof(walk));
que.push(src),dis[src]=0;
int u,v,e;
while(!que.empty()){
u=que.front(),que.pop();
vis[u]=false;
for(e=adj[u];e;e=nxt[e]){
if(cap[e]>0&&dis[u]+cost[e]<dis[v=go[e]]){
dis[v]=dis[u]+cost[e];
if(!vis[v]){
vis[v]=1;
que.push(v);
}
}
}
}
return dis[des]<INF;
}
int dfs(int u,int flow){
if(u==des){
ans+=flow*dis[des];
return flow;
}
walk[u]=1;
int v,e,res=0,delta;
for(e=adj[u];e;e=nxt[e]){
if(!walk[v=go[e]]&&cap[e]>0&&dis[u]+cost[e]==dis[v]){
delta=dfs(v,min(cap[e],flow-res));
if(delta){
cap[e]-=delta;
cap[e^1]-=delta;
res+=delta;
if(res==flow) break;
}
}
}
return res;
}
int slove(){
ans=0;
while(spaf()){
end+=dfs(src,INF);
}
return ans;
}
int main(){
cin>>a>>b>>c>>d;
for(int i=1;i<=b;i++){
int u,v,f,w;
cin>>u>>v>>f>>w;
addEdge(u,v,f,w);
}
src=c;
des=d;
cout<<end<<' '<<slove()<<endl;
return 0;
}