同样是增广路算法，但与最大流dinic算法不同的是： 贪心每次走费用最短路（普通最大流所有边费用都相当于是1，最短路直接bfs就行了） 不能多路増广。 由于是增广路算法，到不能增广时，根据最大流最小割定理，保证当前流是最大流。
代码： （注意：SPFA手写队列要注意大小啊……害得我调了好长时间……干脆用STL好了）
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #define INF 2147483647 using namespace std; const int N = 5005; typedef long long ll; struct node{ int v,f,len; node *next,*rev; }pool[N*20],*h[N]; int cnt; void addedge(int u,int v,int f,int len){ node *p=&pool[++cnt],*q=&pool[++cnt]; p->v=v;p->next=h[u];h[u]=p; p->f=f;p->len=len; p->rev=q; q->v=u;q->next=h[v];h[v]=q; q->f=0;q->len=-len; q->rev=p; } int s,t,n; int d[N],pre[N],vis[N],a[N]; node *pree[N]; queue<int> que; int cost,flow; bool Bfs(){ int u,v; for(int i=1;i<=n;i++) d[i]=a[i]=INF; d[s]=0; que.push(s); vis[s]=1; while(!que.empty()){ u=que.front(); que.pop(); vis[u]=0; for(node *p=h[u];p;p=p->next){ v=p->v; if(p->f>0 && d[v]>d[u]+p->len){ d[v]=d[u]+p->len; pre[v]=u; pree[v]=p; a[v]=min(a[u],p->f); if(vis[v]==0) que.push(v),vis[v]=1; } } } if(d[t]==INF) return false; cost+=d[t]*a[t]; flow+=a[t]; u=t; while(u!=s){ pree[u]->f-=a[t]; pree[u]->rev->f+=a[t]; u=pre[u]; } return true; } void MCMF() { while(Bfs()) ; } int main() { int m,u,v,f,len; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&f,&len); addedge(u,v,f,len); } MCMF(); printf("%d %d\n",flow,cost); return 0; }转载于:https://www.cnblogs.com/lindalee/p/8338392.html
相关资源：数据结构—成绩单生成器