P3381 【模板】最小费用最大流

P3381 【模板】最小费用最大流

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; struct node { int point; int value; int flow; int nxt; }; node line[200000]; int head[10010],tail=-1; void add(int x,int y,int z,int k) { line[++tail].point=y; line[tail].value=k; line[tail].flow=z; line[tail].nxt=head[x]; head[x]=tail; } int max_flow,min_spent; int dis[10010],flow[10010],last[10010]; bool inque[10010]; int pre[10010]; bool SPFA(int begin,int end) { memset(dis,127,sizeof(dis)); memset(inque,0,sizeof(inque)); memset(flow,127,sizeof(flow)); queue<int>q; q.push(begin); inque[begin]=true; pre[end]=-1; dis[begin]=0; while(!q.empty()) { int pas=q.front(); q.pop(); inque[pas]=false; for(int i=head[pas];i!=-1;i=line[i].nxt) if(line[i].flow>0&&dis[line[i].point]>dis[pas]+line[i].value) { dis[line[i].point]=dis[pas]+line[i].value; pre[line[i].point]=pas; last[line[i].point]=i; flow[line[i].point]=min(line[i].flow,flow[pas]); if(!inque[line[i].point]) { q.push(line[i].point); inque[line[i].point]=true; } } } if(pre[end]==-1) return false; return true; } void EK(int begin,int end) { while(SPFA(begin,end)) { int pas=end; max_flow+=flow[end]; min_spent+=dis[end]*flow[end]; while(pas!=begin) { line[last[pas]].flow-=flow[end]; line[last[pas]^1].flow+=flow[end]; pas=pre[pas]; } } } int main() { int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=n;i++) head[i]=-1; int a,b,c,d; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); add(a,b,c,d); add(b,a,0,-1*d); } EK(s,t); printf("%d %d",max_flow,min_spent);; }