#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);; }转载于:https://www.cnblogs.com/Lance1ot/p/9037905.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/101663.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
