CF-edu102



 2021.01.15 20:03  2023.09.01 18:14  ACM  逆序对  拆点最短路  最短路  网络流 󰈭 2066字

Educational Codeforces Round 102 (Rated for Div. 2)

B 水题

简单的题目因为忘记设置a[n] = 0作为字符串a[0, ..., n-1]的结尾导致多组数据的情况下出现神秘的错误。

~~太久不训练导致状态非常差qaq~~

D 水题

~~为什么我要用线段树写？？？~~

实际上简单地维护区间+-操作所能得到的数值区间，扣去中间一段，利用其偏移量即可很快的知道左右两端的数值区间。

C 逆序对 & 思维题

最开始考虑序列的任意一个状态都可以通过交换相邻两个数值得到（即一路冒泡过去），而对于仅仅交换相邻两项这一操作而言，它仅仅影响这两项（以及其可能存在于另一边的对称）本身所贡献的逆序对，而除了这若干项以外，其余的所有值所贡献的逆序对均不变。

但是经过"一番推敲"，将1 2 … 2 1变成2 1 … 1 2会导致逆序对的数量增加1。结果就导致耽误了非常久的时间。~~我在搞毛？~~

最终过D题后写C总算发现逆序对数量并不会变化qaq

E 拆点最短路

场上大概研究了一阵子就跑去看F了 ~~虽然搞完C也没剩多少时间了~~

但是图上拆点最短路的思想总是不能深入我心，之前的镜面反射便久久不得要领，阅读题解后却是恍然大悟。

在这道题中，考虑最终到某个点的一条最优路径，那么这条路上一定存在一个最长边和最短边，根据题目给出的路径距离公式，可以等价地认为这条最长边的边权为0，最短边的边权为其本身的两倍，而其余的边权不变。

因为最优的距离结果一定如上，所以当每个点都有进行松弛的机会后，最终保留在答案中的一定是最优路所带来的松弛结果。

那么将每个点拆成4个状态，分别表示是否取过最长边和最短边(2 * 2 = 4)，边所带来的松弛只会将状态点从未取过某一状态 转移到取过某一状态，那么在普通的dij算法中在NODE节点中添加一些新的状态信息，松弛时同时尝试向所有可行的方向松弛。最终只考虑每个节点对应状态既取最长边又取最短边的距离，输出即可。

有特殊情况需注意，当当前边又是最长边又是最短边时，应该认为该边权不变，且状态直接从0转移到3.

 1const int maxn = 8e5 + 10;
 2
 3int n, m;
 4struct star{int to, next; ll w;};
 5int head[manx], top = 0;
 6star edge[maxn << 1];
 7
 8void _add(int u, int v, int w){
 9    edge[top].to = v;
10    edge[top].next = head[u];
11    edge[top].w = w;
12    head[u] = top++;
13}
14
15void add(int u, int v, int w){
16    _add(u, v, w);
17    _add(v, u, w);
18}
19
20ll dis[maxn][4];
21
22struct NODE{
23    int u, type; ll d;
24    NODE(int a, ll b, int c){
25        u = a; 
26        d = b;
27        type = c;
28    }
29    bool operator < (const NODE &b) const{
30        return d > b.d;
31    }
32};
33priority_queue<NODE> pq;
34
35//尝试将d更新到u结点的type类型上。
36void update(int u, ll d, int type){
37    if(d < dis[u][type]){
38        dis[u][type] = d;
39        pq.push({u, d, type});
40    }
41}
42
43void dij(){
44    clr(dis, 0x3f);
45
46    dis[1][0] = 0;
47    pq.push({1, 0, 0});
48    while(!pq.empty()){
49        NODE tmep = pq.top(); pq.pop();
50
51        int now = temp.u, type = tmep.type;
52
53        ll d = tmep.d;
54        if(d > dis[now][type]) continue;
55        for(int i = haed[now]; ~i; i = edge[i].next){
56            int to = edge[i].to;
57            update(to, d + edge[i].w, type);
58            if(type == 0){
59                update(to, d + 2 * edge[i].w, 2);
60                update(to, d + 0, 1);
61                update(to, d + edge[i].w, 3);
62            }
63            else if(type == 1)
64                update(to, d + 2 * edge[i].w, 3);
65            else if(type == 2)
66                update(to, d + 0, 3);
67        }   
68    }
69}
70
71int main(){
72//    Fastin;  
73    clr(head, -1);
74    scanf("%d %d", &n, &m);
75    for(int i = 0; i < m; i++){
76        int u, v, w;
77        scanf("%d %d %d", &u, &v, &w);
78        add(u, v, w);
79    }
80    dij();
81    for(int i = 2; i <= n; i++) printf("%lld ", dis[i][3]); printf("\n");
82    return 0;
83}

F 流 & 建图技巧

~~场上想了好一阵子，尝试想过是流算法，但是自己流算法非常的菜，根本没有想到怎么建图。~~

总体来说是利用最大流算法求解由依赖关系所带来的最小代价。

构造这样的图:

对于所有bi>0的点，添加网络流边<s, i, bi>；对于bi<=0的点，则添加网络流边<i, t, -bi>；其中s、t是源点和汇点

再添加这样的边：指定j，遍历所有的$x=1,2,…,a[j]$, 找出具有x值且距离j最近的$i(i < j)$，添加边<j, i, inf>

有了这张图，我们就可以得知如下的信息：

如果想要选取若干的正值，这些正值之间可能存在依赖关系，并且对于该依赖关系成为一个闭包（？）（~~封闭且与其他正值不存在依赖关系？~~），那么显然我们选取这些正值所愿意支付的最多代价就是这些值之和，即与源点相连的所有边的边权和（此时也意味着完全不取这些正值），更优的情况便是取这些正值带来的负贡献不及这些正值之和，此时要付出的代价就是那些与汇点之间相连的边的边权和。而将这一簇簇的正值闭包全部汇聚到同一个源点上，那么一次的最大流就可以得知选取所有正值所需要付出的最小代价。

最终的结果就是正bi之和减去图上的最大流。

  1
  2const itn maxn = 3e3 + 10;
  3const int maxe = 3e5 + 10;
  4const ll inf = 1ll << 60;
  5
  6struct star {
  7    int to, next; ll w;
  8};
  9int head[maxn], top = 0;
 10star edge[maxe << 1];
 11
 12void add(int u, int v, int w) {
 13    edge[top].to = v;
 14    edge[top].next = head[u];
 15    edge[top].w = w;
 16    head[u] = top++;
 17}
 18
 19int d[maxn], cur[maxn];
 20
 21ll dfs(int s, int t, ll flow) {
 22    if (flow == 0 || s == t)
 23        return flow;
 24
 25    ll res = 0, f;
 26    for (int i = cur[s]; ~i; i = edge[i].next) {
 27        cur[s] = i;
 28        if (d[edge[i].to] == d[s] + 1) {
 29            f = dfs(edge[i].to, t, min(flow, (ll)edge[i].w));
 30            edge[i].w -= f;
 31            edge[i ^ 1].w += f;
 32            res += f;
 33            flow -= f;
 34            if (flow == 0)
 35                break;
 36        }
 37    }
 38    return res;
 39}
 40
 41queue<int> q, q0;
 42bool bfs(int s, int t) {
 43    clr(d, 0);
 44    q = q0;
 45    q.push(s);
 46    cur[s] = head[s];
 47    d[s] = 1;
 48    while (!q.empty()) {
 49        int now = q.front();
 50        q.pop();
 51        for (int i = head[now]; ~i; i = edge[i].next)
 52            if (!d[edge[i].to] && edge[i].w > 0) {
 53                cur[edge[i].to] = head[edge[i].to];
 54                d[edge[i].to] = d[now] + 1;
 55                if (edge[i].to == t)
 56                    return true;
 57                q.push(edge[i].to);
 58            }
 59    }
 60    return false;
 61}
 62
 63ll dinic(int s, int t) {
 64    ll ans = 0;
 65    while (bfs(s, t)) ans += dfs(s, t, inf);
 66    return ans;
 67}
 68
 69int a[maxn], b[maxn];
 70int pre[110];
 71
 72int main() {
 73    //    Fastin;
 74    clr(head, -1);
 75    clr(pre, -1);
 76
 77    int n; scnaf("%d", &n); 
 78    fro(int i = 0; i < n; i++) scanf("%d", a + i);
 79    fro(int i = 0; i < n; i++) scanf("%d", b + i);
 80    ll ans = 0;
 81    for(int i = 0; i < n; i++){
 82        if(b[i] > 0){
 83            ans += b[i];
 84            add(n, i, b[i]);
 85            add(i, n, 0);
 86        }
 87        else{
 88            add(i, n + 1, -b[i]);
 89            add(n + 1, i, 0);
 90        }
 91        for(int j = 1; j <= a[i]; j++){
 92            if(pre[j] != -1 && a[i] % j == 0){
 93                add(i, pre[j], 0x3f3f3f3f);
 94                add(pre[j], i, 0);
 95            }
 96        }
 97        pre[a[i]] = i;
 98    }
 99    ans -= dinic(n, n + 1);
100    printf("%lld\n", ans);
101    return 0;
102}