题目链接：
把bfs变成spfa
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn = 1000000 + 10; 8 int n, m, s, t, maxflow, mincost, dis[maxn], flow[maxn], pre[maxn], last[maxn]; 9 struct edge{10 int to, next, cost, flow;11 }e[maxn<<2];12 int head[maxn], cnt = -1;13 bool vis[maxn];14 queue q;15 void add(int u, int v, int w, int c)16 {17 e[++cnt].next = head[u];18 e[cnt].to = v;19 e[cnt].cost = c;20 e[cnt].flow = w;21 head[u] = cnt;22 23 e[++cnt].next = head[v];24 e[cnt].to = u;25 e[cnt].cost = -c;26 e[cnt].flow = 0;27 head[v] = cnt;28 }29 bool SPFA(int s, int t)30 {31 memset(dis, 0x7f, sizeof(dis));32 memset(flow, 0x7f, sizeof(flow));33 memset(vis, 0, sizeof(vis));34 q.push(s); pre[t] = -1; vis[s] = 1; dis[s] = 0;35 while(!q.empty())36 {37 int now = q.front(); q.pop();38 vis[now] = 0;39 for(int i = head[now]; i != -1; i = e[i].next)40 {41 if(e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost)42 {43 dis[e[i].to] = dis[now] + e[i].cost;44 pre[e[i].to] = now;45 last[e[i].to] = i;46 flow[e[i].to] = min(flow[now], e[i].flow);47 if(!vis[e[i].to])48 {49 q.push(e[i].to);50 vis[e[i].to] = 1;51 }52 }53 }54 }55 return pre[t] != -1;56 }57 void MCMF(int s, int t)58 {59 while(SPFA(s, t))60 {61 int now = t;62 maxflow += flow[t];63 mincost += flow[t] * dis[t];64 while(now != s)65 {66 e[last[now]].flow -= flow[t];67 e[last[now]^1].flow += flow[t];68 now = pre[now];69 }70 }71 }72 int main()73 {74 memset(head, -1, sizeof(head));75 scanf("%d%d%d%d",&n,&m,&s,&t);76 for(int i = 1; i <= m; i++)77 {78 int u, v, w, c;79 scanf("%d%d%d%d",&u,&v,&w,&c);80 add(u, v, w, c);81 }82 MCMF(s, t);83 printf("%d %d\n",maxflow, mincost);84 return 0;85 }