最小费用最大流

 1 #include<bits/stdc++.h>
 2 
 3 struct node{
 4     ll to,from,val,cost;
 5 }e[N];
 6 int t=1;
 7 void add(int u,int v,int cap,int cost){
 8     t++;
 9     e[t].to=v;
10     e[t].from=u;
11     e[t].cap=cap;
12     e[t].cost=cost;
13     e[t].n=h[u];
14     h[u]=t;
15 }
16 
17 bool bfs()
18 {
19     memset(d,0x3f,sizeof(d));
20     memset(b,0,sizeof(b));
21     queue<int> q;
22     while(!q.empty())
23         q.pop();
24     for(int i=1;i<=n;i++)
25     {
26         fa[i]=-1;
27     }
28     vis[s]=1;d[s]=0;f[s]=0;
29     flow[s]=inf;q.push(s);
30     while(q.size())
31     {
32         int u=q.front();
33         q.pop();
34         vis[u]=0;
35         for(int i=head[u];i;i=e[i].n)
36         {
37             int v=e[i].to;
38             if(e[i].cap>0&&d[v]>d[u]+e[i].cost)
39             {
40                 d[v]=d[u]+e[i].cost;
41                 f[v]=u;
42                 xb[v]=i;
43                 flow[v]=min(flow[u],e[i].cap);
44                 if(!vis[v]){
45                     vis[v]=1;
46                     q.push(v);}
47             }
48         }
49     }
50     return d[t]<inf;
51 }
52 void max_flow()
53 {
54     while(bfs())
55     {
56         int k=t;
57         while(k!=s)
58         {
59             e[xb[k]].cap-=flow[t];
60             e[xb[k]^1].cap+=flow[t];
61             k=f[k];
62         }
63         tot+=flow[t];
64         sum+=flow[t]*d[t];
65     }
66 }
67 
68 add(u,v,cap,cost);
69 add(v,u,0,-cost);