最大最小费用流

题目在这里https://hihocoder.com/problemset/problem/1591?sid=1197871

理解题目，用费用流以后，就抄个模板，建好图，跑就行。

源代码在这里http://blog.csdn.net/jzq233jzq/article/details/73123089

下面贴上代码，需要的时候，拷贝一下就行。

  1 #include<bits/stdc++.h>
  2 #define pb push_back
  3 typedef long long ll;
  4 using namespace std;
  5 typedef pair<int, int> pii;
  6 const int maxn = 1e3 + 10;
  7 bool vis[200001];int dist[200001];
  8 //解释一下各数组的含义：vis两个用处：spfa里的访问标记，増广时候的访问标记，dist是每个点的距离标号
  9 int n,m,s,t,ans=0;
 10 //s是起点，t是终点，ans是费用答案
 11 int nedge=-1,p[200001],c[200001],cc[200001],nex[200001],head[200001];
 12 //这里是边表，解释一下各数组的含义：p[i]表示以某一点出发的编号为i的边对应点，c表示编号为i的边的流量，cc表示编号为i的边的费用，nex和head不说了吧。。。
 13 inline void addedge(int x,int y,int z,int zz){
 14     p[++nedge]=y;c[nedge]=z;cc[nedge]=zz;nex[nedge]=head[x];head[x]=nedge;
 15 }
 16 //建边（数组模拟边表倒挂）
 17 inline bool spfa(int s,int t){
 18     memset(vis,0,sizeof vis);
 19     for(int i=0;i<=n;i++)dist[i]=1e9;dist[t]=0;vis[t]=1;
 20 //首先SPFA我们维护距离标号的时候要倒着跑，这样可以维护出到终点的最短路径
 21     deque<int>q;q.push_back(t);
 22 //使用了SPFA的SLF优化（SLF可以自行百度或Google）
 23     while(!q.empty()){
 24         int now=q.front();q.pop_front();
 25         //cout << now << " ddd " << endl;
 26         for(int k=head[now];k>-1;k=nex[k])if(c[k^1]&&dist[p[k]]>dist[now]-cc[k]){
 27 //首先c[k^1]是为什么呢，因为我们要保证正流，但是SPFA是倒着跑的，所以说我们要求c[k]的对应反向边是正的，这样保证走的方向是正确的
 28             dist[p[k]]=dist[now]-cc[k];
 29 //因为已经是倒着的了，我们也可以很清楚明白地知道建边的时候反向边的边权是负的，所以减一下就对了（负负得正）
 30             if(!vis[p[k]]){
 31                 vis[p[k]]=1;
 32                 if(!q.empty()&&dist[p[k]]<dist[q.front()])q.push_front(p[k]);else q.push_back(p[k]);
 33 //SLF优化
 34             }
 35         }
 36         vis[now]=0;
 37     }
 38     return dist[s]<1e9;
 39 //判断起点终点是否连通
 40 }
 41 inline int dfs(int x,int low){
 42 //这里就是进行増广了
 43     if(x==t){vis[t]=1;return low;}
 44     int used=0,a;vis[x]=1;
 45 //这边是不是和dinic很像啊
 46     for(int k=head[x];k>-1;k=nex[k])if(!vis[p[k]]&&c[k]&&dist[x]-cc[k]==dist[p[k]]){
 47 //这个条件就表示这条边可以进行増广
 48         a=dfs(p[k],min(c[k],low-used));
 49         if(a)ans+=a*cc[k],c[k]-=a,c[k^1]+=a,used+=a;
 50 //累加答案，加流等操作都在这了
 51         if(used==low)break;
 52     }
 53     return used;
 54 }
 55 inline int costflow(){
 56     int flow=0;
 57     while(spfa(s,t)){
 58 //判断起点终点是否连通，不连通说明满流，做完了退出
 59         //cout <<"asd" << endl;
 60         vis[t]=1;
 61         while(vis[t]){
 62             memset(vis,0,sizeof vis);
 63             flow+=dfs(s,1e9);
 64 //一直増广直到走不到为止（这样也可以省时间哦）
 65         }
 66     }
 67     return flow;//这里返回的是最大流，费用的答案在ans里
 68 }
 69 int tn, tmc;
 70 int tc[110];
 71 int te[110][110];
 72 int ta[110][110];
 73 int solve()
 74 {
 75     cin >> tn;
 76     for (int i = 1; i <= tn; i++) cin >>tc[i];
 77     cin >> tmc;
 78     int x, y;
 79     for (int i = 0; i < tmc; i++) {
 80         cin >> x >> y;
 81         te[x][y] = 1; te[y][x] = -1;
 82     }
 83     for (int i = 1; i <= tn; i++) {
 84         for (int j = 1; j <= tn; j++)
 85             cin >> ta[i][j];
 86     }
 87     memset(nex,-1,sizeof nex);memset(head,-1,sizeof head);
 88     //scanf("%d%d%d%d",&n,&m,&s,&t);
 89     n = tn * (tn - 1) / 2 + tn + 2 + 1;
 90     s = n - 1; t = s - 1;
 91     for (int i = 1; i <= tn; i++) {
 92         addedge(i, t, tc[i], 0);addedge(t, i, 0, 0);
 93     }
 94     int cur = tn;
 95     for (int i = 1; i <= tn; i++) {
 96         for(int j = i + 1; j <= tn; j++) {
 97             cur++;
 98             addedge(s, cur, 1, 0); addedge(cur, s, 0, 0);
 99             if(te[i][j] > 0) {
100                 addedge(cur, i, 1, -ta[i][j]);addedge(i, cur, 0, ta[i][j]);
101                 //cout << cur << " " << i <<" " << j <<" " <<ta[i][j] << endl;
102             } else if(te[i][j] == 0) {
103                 addedge(cur, i, 1, -ta[i][j]);addedge(i, cur, 0, ta[i][j]);
104                 addedge(cur, j, 1, -ta[j][i]);addedge(j, cur, 0, ta[j][i]);
105             } else {
106                 addedge(cur, j, 1, -ta[j][i]);addedge(j, cur, 0, ta[j][i]);
107             }
108         }
109     }
110     /*
111     for(int i=1;i<=m;i++){
112         int x,y,z,zz;scanf("%d%d%d%d",&x,&y,&z,&zz);
113         addedge(x,y,z,zz);addedge(y,x,0,-zz);
114     } */
115     costflow();
116     //printf("%d ",costflow());
117     printf("%d",-ans);
118     return 0;
119 }
120 
121 int main() {
122     freopen("test.in", "r", stdin);
123     //freopen("test.out", "w", stdout);
124     solve();
125     return 0;
126 }

View Code

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int N = 103;
  5 int match[N][N], matchIdx;
  6 
  7 const int MAXN = 10011;
  8 const int MAXM = 100011;
  9 const int INF = (1 << 30);
 10 
 11 struct Edge {
 12     int next, from, to, cap, cost;
 13 };
 14 
 15 struct MCMF {
 16     Edge edge[MAXM];
 17     int head[MAXN], countedge;
 18 
 19     void Init(int N) {
 20         this->N = N;
 21         memset(head, -1, sizeof(head));
 22         countedge = 0;
 23     }
 24 
 25     int N;
 26     int inq[MAXN], dis[MAXN], pre[MAXN], ad[MAXN];
 27 
 28     void AddEdge(const int& start, const int& end, const int& cap,
 29                  const int& cost) {
 30         edge[countedge].to = end;
 31         edge[countedge].from = start;
 32         edge[countedge].next = head[start];
 33         edge[countedge].cap = cap;
 34         edge[countedge].cost = cost;
 35         head[start] = countedge++;
 36         edge[countedge].to = start;
 37         edge[countedge].from = end;
 38         edge[countedge].next = head[end];
 39         edge[countedge].cap = 0;
 40         edge[countedge].cost = -cost;
 41         head[end] = countedge++;
 42     }
 43 
 44     bool BF(int s, int t, int& cost) {
 45         int i;
 46         for (i = 0; i < N; i++) dis[i] = INF;
 47         memset(inq, 0, sizeof(inq));
 48         dis[s] = 0;
 49         inq[s] = 1;
 50         pre[s] = -1;
 51         ad[s] = INF;
 52 
 53         queue<int> que;
 54         que.push(s);
 55         int u, v, temp;
 56         while (!que.empty()) {
 57             u = que.front();
 58             que.pop();
 59             inq[u] = 0;
 60             for (temp = head[u]; temp != -1; temp = edge[temp].next) {
 61                 v = edge[temp].to;
 62                 if (edge[temp].cap && dis[v] > dis[u] + edge[temp].cost) {
 63                     dis[v] = dis[u] + edge[temp].cost;
 64                     pre[v] = temp;
 65                     ad[v] = min(ad[u], edge[temp].cap);
 66                     if (!inq[v]) {
 67                     inq[v] = 1;
 68                     que.push(v);
 69                     }
 70                 }
 71             }
 72         }
 73         if (dis[t] == INF) return false;
 74         cost += dis[t] * ad[t];
 75         u = t;
 76         while (u != s) {
 77             edge[pre[u]].cap -= ad[t];
 78             edge[pre[u] ^ 1].cap += ad[t];
 79             u = edge[pre[u]].from;
 80         }
 81         return true;
 82     }
 83 
 84     int MinC(int s, int t) {
 85     int cost = 0;
 86     while (BF(s, t, cost))
 87         ;
 88     return cost;
 89     }
 90 }f;
 91 
 92 int score[N];
 93 bool ban[N][N];
 94 int u[10011], v[10011];
 95 int add[N][N];
 96 
 97 int main() {
 98     int n;
 99     scanf("%d", &n);
100 
101     f.Init(n + n * (n - 1) / 2 + 2);
102     int S = n + n * (n - 1) / 2, T = S + 1;
103     for (int i = 0; i < n; i++) {
104         scanf("%d", &score[i]);
105         f.AddEdge(S, i, score[i], 0);
106     }
107 
108     matchIdx = n;
109     for (int i = 0; i < n; i++) {
110         for (int j = i + 1; j < n; j++) {
111             match[i][j] = matchIdx++;
112             f.AddEdge(match[i][j], T, 1, 0);
113         }
114     }
115 
116     int see;
117     scanf("%d", &see);
118     for(int i = 0; i < see; i++) {
119         scanf("%d%d", &u[i], &v[i]);
120         u[i]--;
121         v[i]--;
122         ban[v[i]][u[i]] = true;
123     }
124 
125     for(int i = 0; i < n; i++) {
126         for(int j = 0; j < n; j++) {
127             scanf("%d", &add[i][j]);
128             if(i == j) {
129                 continue;
130             }
131             if(!ban[i][j]) {
132                 f.AddEdge(i, match[min(i, j)][max(i, j)], 1, -add[i][j]);
133             }
134         }
135     }
136 
137     cout << -f.MinC(S, T) << endl;
138 
139     return 0;
140 }

View Code

hihocode offer收割赛33 第三题，第二名，比较好的模板

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 200 + 5;
  6 const int NN = N * N * 2 + 5;
  7 const int M = NN * 4 + 5;
  8 
  9 struct Edge {
 10   int u, v, c, cost, nxt;
 11   Edge() {}
 12   Edge(int _u, int _v, int _c, int _cost, int _nxt)
 13     : u(_u), v(_v), c(_c), cost(_cost), nxt(_nxt) {}
 14 } es[M];
 15 
 16 int head[NN], from[NN], dp[NN], tot;
 17 
 18 int n;
 19 int x[N][N];
 20 
 21 void addEdge(int u, int v, int c, int cost) {
 22   es[tot] = Edge(u, v, c, cost, head[u]);
 23   head[u] = tot++;
 24 }
 25 
 26 void addDoubleEdge(int u, int v, int c, int cost) {
 27   addEdge(u, v, c, cost);
 28   addEdge(v, u, 0, -cost);
 29 }
 30 
 31 int spfa(int s, int t) {
 32   deque <int> de;
 33   memset(dp, -1, sizeof dp);
 34   dp[s] = 0;
 35   de.push_back(s);
 36   while (!de.empty()) {
 37     int u = de.front();
 38     de.pop_front();
 39     for (int i = head[u]; i != -1; i = es[i].nxt) {
 40       if (es[i].c == 0)
 41         continue;
 42       int v = es[i].v;
 43       if (dp[v] < dp[u] + es[i].cost) {
 44         dp[v] = dp[u] + es[i].cost;
 45         from[v] = i;
 46         de.push_back(v);
 47       }
 48     }
 49   }
 50   if (dp[t] == -1)
 51     return dp[t];
 52   int temp = t;
 53   while (temp != s) {
 54     int id = from[temp];
 55     --es[id].c;
 56     ++es[id ^ 1].c;
 57     temp = es[id].u;
 58   }
 59   return dp[t];
 60 }
 61 
 62 int mcmf(int s, int t) {
 63   int ret = 0;
 64   while (true) {
 65     int add = spfa(s, t);
 66     if (add == -1)
 67       break;
 68     ret += add;
 69   }
 70   return ret;
 71 }
 72 
 73 int main()
 74 {
 75   ios::sync_with_stdio(false);
 76   cin.tie(nullptr); cout.tie(nullptr);
 77 
 78   cin >> n;
 79   for (int i = 0; i < n; ++i)
 80     for (int j = 0; j < n; ++j)
 81       cin >> x[i][j];
 82   
 83   int all = n * n;
 84   tot = 0;
 85   memset(head, -1, sizeof head);
 86   for (int i = 0; i < n; ++i) {
 87     for (int j = 0; j < n; ++j) {
 88       int c = 1;
 89       if (i == 0 && j == 0)
 90         c = 2;
 91       if (i == n - 1 && j == n - 1)
 92         c = 2;
 93       addDoubleEdge(i * n + j, i * n + j + all, c, x[i][j]);
 94       if (i + 1 < n)
 95         addDoubleEdge(i * n + j + all, (i + 1) * n + j, 1, 0);
 96       if (j + 1 < n)
 97         addDoubleEdge(i * n + j + all, i * n + j + 1, 1, 0);
 98     }
 99   }
100   int s = all + all, t = s + 1;
101   addDoubleEdge(s, 0, 2, 0);
102   addDoubleEdge(all + all - 1, t, 2, 0);
103   cout << mcmf(s, t) << '
';
104   return 0;
105 }

View Code