1 #include<functional>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 #include<queue>
  9 #define REP(i, n) for(int i=0; i<n; i++)
 10 #define FF(i, a, b) for(int i=a; i<b; i++)
 11 #define CLR(a, b) memset(a, b, sizeof(a))
 12 #define PB push_back
 13 using namespace std;
 14 
 15 const int MAXN = 455;
 16 const int MAXE = MAXN*MAXN/2;
 17 const int INF = 1e9;
 18 struct ZKW_flow
 19 {
 20     int st, ed, ecnt, n;
 21     int head[MAXN];
 22     int cap[MAXE], cost[MAXE], to[MAXE], next[MAXE], dis[MAXN]; ;
 23 
 24     void init()
 25     {
 26         memset(head, 0, sizeof(head));
 27         ecnt = 2;
 28     }
 29 
 30     void AddEdge(int u, int v, int cc, int ww)
 31     {
 32         cap[ecnt] = cc;
 33         cost[ecnt] = ww;
 34         to[ecnt] = v;
 35         next[ecnt] = head[u];
 36         head[u] = ecnt++;
 37         cap[ecnt] = 0;
 38         cost[ecnt] = -ww;
 39         to[ecnt] = u;
 40         next[ecnt] = head[v];
 41         head[v] = ecnt++;
 42     }
 43 
 44     void SPFA()
 45     {
 46         REP(i, n+1) dis[i] = INF;
 47         priority_queue<pair<int, int> > Q;
 48         dis[st] = 0;
 49         Q.push(make_pair(0, st));
 50         while(!Q.empty())
 51         {
 52             int u = Q.top().second, d = -Q.top().first;
 53             Q.pop();
 54             if(dis[u] != d) continue;
 55             for(int p = head[u]; p; p = next[p])
 56             {
 57                 int &v = to[p];
 58                 if(cap[p] && dis[v] > d + cost[p])
 59                 {
 60                     dis[v] = d + cost[p];
 61                     Q.push(make_pair(-dis[v], v));
 62                 }
 63             }
 64         }
 65         REP(i, n+1) dis[i] = dis[ed] - dis[i];
 66     }
 67 
 68     int minCost, maxFlow;
 69     bool use[MAXN];
 70 
 71     int add_flow(int u, int flow)
 72     {
 73         if(u == ed)
 74         {
 75             maxFlow += flow;
 76             minCost += dis[st] * flow;
 77             return flow;
 78         }
 79         use[u] = true;
 80         int now = flow;
 81         for(int p = head[u]; p; p = next[p])
 82         {
 83             int &v = to[p];
 84             if(cap[p] && !use[v] && dis[u] == dis[v] + cost[p])
 85             {
 86                 int tmp = add_flow(v, min(now, cap[p]));
 87                 cap[p] -= tmp;
 88                 cap[p^1] += tmp;
 89                 now -= tmp;
 90                 if(!now) break;
 91             }
 92         }
 93         return flow - now;
 94     }
 95 
 96     bool modify_label()
 97     {
 98         int d = INF;
 99         REP(u, n+1) if(use[u])
100             for(int p = head[u]; p; p = next[p])
101             {
102                 int &v = to[p];
103                 if(cap[p] && !use[v]) d = min(d, dis[v] + cost[p] - dis[u]);
104             }
105         if(d == INF) return false;
106         REP(i, n+1) if(use[i]) dis[i] += d;
107         return true;
108     }
109 
110     int Mincost(int ss, int tt, int nn)
111     {
112         st = ss, ed = tt, n = nn;
113         minCost = maxFlow = 0;
114         SPFA();
115         while(true)
116         {
117             while(true)
118             {
119                 CLR(use, 0);
120                 if(!add_flow(st, INF)) break;
121             }
122             if(!modify_label()) break;
123         }
124         return minCost;
125     }
126 } solver;

ZKW_flow(费用流模板)

优质内容筛选与推荐>>
1、如何在windows的DOS窗口中正常显示中文(UTF-8字符)
2、**指针的指针，引用
3、两个css之间的切换
4、java设计模式--结构型模式--装饰模式
5、mac终端terminal快捷键