RT,费用流,现已知是SPFA(代码中是BFS)出问题了,求调
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define dbout cerr<<"[DeBug]:"
#define mem(x,y) memset(x,y,sizeof(x))
inline int read()
{
int x(0),f(1);char c=getchar();
while(c>'9'||c<'0')f=c=='-'?-1:1,c=getchar();
while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
return f*x;
}
const int INF=0x3f3f3f3f,N=5010,M=50010;
int co;
namespace Dinic
{
int head[N],to[M],edge[M],nxt[M],tot,now[M],cost[M];
int n,m,s,t;
int dis[N];
bool vis[N];
void add(int x,int y,int z,int zz,int co)
{
// cerr<<x<<" "<<y<<" "<<z<<endl;
to[++tot]=y,edge[tot]=z,cost[tot]=co,nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,edge[tot]=zz,cost[tot]=-co,nxt[tot]=head[y],head[y]=tot;
}
bool bfs()
{
cerr<<"BFS"<<endl;
memset(dis,0x3f,sizeof(dis));
queue<int>q;
q.push(s),dis[s]=0,vis[s]=1,now[s]=head[s];
while(!q.empty())
{
int x=q.front();
q.pop();vis[x]=0;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(edge[i]&&dis[y]>dis[x]+cost[i])
{
now[y]=head[y];
dis[y]=dis[x]+cost[i];
if(!vis[y])q.push(y),vis[y]=1;
}
}
}
return dis[t]!=INF;
}
int dfs(int x,int f)
{
cerr<<"DFS"<<endl;
if(x==t)return f;
int lft=f,k;
for(int& i=now[x];i;i=nxt[i])
if(edge[i]&&dis[to[i]]==dis[x]+cost[i])
{
int y=to[i];
k=dfs(y,min(edge[i],lft));
if(!k){dis[y]=0;continue;}
co+=k*cost[i];
edge[i]-=k;
edge[i^1]+=k;
lft-=k;
if(!lft)return f-lft;
}
return f-lft;
}
int dinic()
{
int ans=0;
while(bfs())
ans+=dfs(s,INF);
return ans;
}
void limit()
{
n=read();m=read();s=read();t=read();
tot=1;
for(int i=1;i<=m;i++)
{
int a=read(),b=read(),c=read(),d=read();
add(a,b,c,0,d);
}
}
}
int main()
{
fr(P3381_8);
Dinic::limit();
int x=Dinic::dinic();
printf("%d %d",x,co);
return 0;
}