Educational Codeforces Round 139

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
F(费用流, 上下界网络流)

https://codeforces.com/contest/1766

F. MCF

n 点 m边 网络求一个最大流,最小费用 方案

且满足每条边上 实际流 与 其容量 奇偶性一致

输出方案, 或不存在

范围

n 100

m 200

容量 [1,100]

单位代价 wi [-100,100]

我的思路

想着把奇数处理掉, 剩下就是容量处以2, 费用乘以2的问题了

但不会处理奇数, 想到可以每个点出度入度, 但具体也不会

题解

一样, 也是如果处理了奇数, 偶数就好办了

考虑 2k+1, 拆成 2k容量和 1容量的,且1容量的强制跑满(所以实际不需要建立这条1容量的边, 然后所有容量除以2)

// 这有个问题就是 这些指定跑满的流的来源 和 去向

如何具体的去除 “1容量”的边, 还真和点有关系, 计算点和 容量1的边的连接个数 是否是偶数!!!!!!!!!!!! 否则不可能有方案(源和汇例外, 但 源汇肯定需要同奇偶, 为了简化判断, 在源为奇数个1边相连时,还可以加一条 源到汇的 1容量 0单位代价的 边 )

// 我还想了半天 奇的流导致 偶的容量 剩余变成奇数…….. 傻了

对于每个点, 考虑 多少 excess flow (多少个奇数入弧), 如果直接删掉这些1边, 那么这个容量(必须满的流量)也会消失,

额外增加新的 源和汇 S,T, 这样把 excess flow 转换成 S -> 点,(注意要除以2), 同样 奇出度 换成 点 -> t

方案1 增加 n -> 1 无限容量的边 like “flow with lower bounds”???? 这个需要你注意负环的问题

方案2 增加 s -> 1, n -> t的无限容量, 然后让 单流代价 -1e9, 然后对 s -> t 做 最大流最小费用

// 好怪啊, 这样拆 合理性呢

原来就是 Maximum Flows with Edge Demands 的知识

flow with lower bounds / Maximum Flows with Edge Demands

https://codeforces.com/blog/entry/48611

https://oi-wiki.org/graph/flow/bound/

计算的 点的出入下界的差值, 来建立额外的S’,T’相连接, 还有一个从 原来的汇T 到 源S的无限大容量 的边

代码

https://codeforces.com/contest/1766/submission/185738938

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;}

template<typename T, T INF>
class MinCostFlow{
  public:
    struct Edge {
      int u;
      int v;
      T cap;
      T cost;
    };
    int n ; // 点 1-index
    vector<Edge> e; // e = {u,v,cap,cost}
    int eidx = 0;
    vector<vector<pair<int,int> > > u2ve;
    vector<T> dis;
    vector<int> pre;

    MinCostFlow(int n):n(n){ u2ve.resize(n); } // 0-index
    void edge(int u,int v,T cap,T cost) {
      u2ve[u].push_back({v,e.size()});
      e.push_back(Edge{u,v,cap,cost});
      u2ve[v].push_back({u,e.size()});
      e.push_back(Edge{v,u,0,-cost});
    }
    bool spfa(int s,int t) {
      queue<int> q;
      vector<bool> in_queue(n,false); // 是否在queue中
      pre = vector<int>(n,-1); // 前向 边id
      dis = vector<T>(n,INF); // 距离 = 单位cost之和!!! TODO 不要yong magic number, 增加一个变量记录
      in_queue[s] = true;
      dis[s] = 0;
      q.push(s);
      while(!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        for(auto [v,ei]:u2ve[u]){
          if(e[ei].cap && dis[v] > dis[u] + e[ei].cost) { // 这里实现了最小, 不能有负环
            dis[v] = dis[u] + e[ei].cost;
            pre[v] = ei;
            if(!in_queue[v]) {
              q.push(v);
              in_queue[v]=true;
            }
          }
        }
      }
      return dis[t] != INF and dis[t] < 0; // min cost ignore >= 0 cost
    }

    // return {最小费用,最大流}
    pair<T,T> flow(int s,int t) {
      T flow = 0; // 总流量
      T mincost = 0;
      while(spfa(s,t)) {
        T minflow = INF;
        for(int ei=pre[t];ei!=-1;ei=pre[e[ei].u]){
          if(e[ei].cap < minflow) minflow = e[ei].cap;
        }
        flow += minflow;
        for(int ei=pre[t];ei!=-1;ei=pre[e[ei].u]) {
          e[ei].cap -= minflow;
          e[ei^1].cap += minflow;
        }
        mincost += dis[t] * minflow;
      }
      return {mincost,flow}; // 最大流
    }
    pair<T,T> getEdgeFlowCap(int edgeid){ // follow the add order, return {flow, cap}
      assert(edgeid*2 < (int)e.size());
      return {e[edgeid*2+1].cap, e[edgeid*2].cap+e[edgeid*2+1].cap };
    }
};


int main(){
  const ll INF = 0x3f3f3f3f; // > 200 00

  int n=read();
  int m=read();
  vector<int> du(n);
  vector<int> edgecap(m);
  const int S=n;
  const int T=S+1;
  MinCostFlow <ll,0x3f3f3f3f3f3f3f3f>g(T+1);
  rep(i,0,m){ // [0,m)
    int u=read()-1;
    int v=read()-1;
    int cap=edgecap[i]=read();
    int cost=read();
    if(cap&1){ // u -> v
      du[u]--;
      du[v]++;
    }
    g.edge(u,v,cap/2,cost*2);
  }
  if(du[0]&1) { // 0 -> n-1
    du[0]--;
    du[n-1]++;
  }
  rep(u,0,n) if(du[u]&1){
    printf("Impossible\n");
    return 0;
  }
  const ll off=-30000; // 优先级高, 一定要填满
  // [m,m+2)
  g.edge(S  ,0,INF,0); // S' -> S
  g.edge(n-1,T,INF,0); // T  -> T'
  // [m+2,m+2+n)
  rep(u,0,n){
    if(du[u] >= 0) g.edge(S,u, du[u]/2,off);
    else           g.edge(u,T,-du[u]/2,off);
  }
  g.flow(S,T);
  rep(eid,m+2,m+2+n) {
    auto [flow,cap] = g.getEdgeFlowCap(eid);
    if(flow != cap){
      printf("Impossible\n");
      return 0;
    }
  }
  printf("Possible\n");
  rep(eid,0,m) printf("%lld ",g.getEdgeFlowCap(eid).first*2+(edgecap[eid]&1));
  return 0;
}

总结

F

没学过 Maximum Flows with Edge Demands 要怎么搞,学了一手

然后 最小费用流 和 最大流最小费用流一样, 不过是忽略 距离非负的路径

参考

官方