最小费用最大流模板

 1 ///最小费用最大流模板
 2 bool spfa()
 3 {
 4      fill(vs,vs+n+2,false);
 5      fill(d,d+n+2,inf);
 6      fill(father,father+n+2,-1);
 7      queue<int>q;
 8      d[0]=0;
 9      q.push(0);
10      while (!q.empty())
11      {
12          int u=q.front();
13          q.pop();
14          vs[u]=false;
15          for (int i=head[u];i!=-1;i=eage[i].next)
16          {
17              int v=eage[i].v;
18              if (eage[i].cap&&d[v]>d[u]+eage[i].cost)
19              {
20                  d[v]=d[u]+eage[i].cost;
21                  father[v]=i;
22                  if (!vs[v])
23                  {
24                      vs[v]=true;
25                      q.push(v);
26                  }
27              }
28          }
29      }
30      if (father[n+1]==-1) return false;
31      return true;
32 }
33 
34 int solve()
35 {
36     int ans=0;
37     while (spfa())
38     {
39         ans+=d[n+1];
40         int u=n+1;
41         while (u!=0)
42         {
43             int i=father[u];
44             eage[i].cap--;
45             eage[i^1].cap++;
46             u=eage[i].u;
47         }
48     }
49     return ans;
50 }