代码编织梦想

在这里插入图片描述

思路:

容易把答案转化为 ∑ s i w i + ∑ t i ( w x − w y ) \sum{s_iw_i}+\sum{t_i(w_x-w_y)} siwi+ti(wxwy),然后我们设初始代价为 − ∑ ∣ s i ∣ w i -\sum{|s_i|w_i} siwi,然后考虑建模。
如果Si大于0,则源点向i连一条流量为2SiW的边,代表割掉这条边(也就是让i为w)要多付出的代价,向汇点连0的边。Si小于0,汇点向i连2SiW的边,向汇点连0的边。
然后对于wx-wy,则直接连2wti的双向边。
考虑限制,若果是<,则强制x和y的w,分别连inf边。
如果是=,则之间连inf边
如果是<=,则y向x连inf边。
然后做最小割就是答案。

c o d e code code

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>
#define ll long long


using namespace std;

const ll MAXN = 550, inf = 1e12;

ll Q, tot;
ll n, w, p, q, S, T;
ll s[MAXN * 3], a[MAXN * 3];
ll crn[MAXN * 3], dep[MAXN * 3], head[MAXN * 3];
struct edge {
    ll to, next, w, op;
} b[MAXN * MAXN * 21];
ll MB[MAXN][MAXN];
queue<ll> G;

void add(ll x, ll y, ll w) {
    b[++tot] = (edge){ y, head[x], w, tot + 1 };
    head[x] = tot;
    b[++tot] = (edge){ x, head[y], 0, tot - 1 };
    head[y] = tot;
}

bool bfs() {
    for (int i = 1; i <= T; i++) crn[i] = head[i], dep[i] = 0;
    while (!G.empty()) G.pop();
    G.push(S);
    dep[S] = 1;
    while (!G.empty()) {
        int now = G.front();
        G.pop();
        for (int i = head[now]; i; i = b[i].next)
            if (b[i].w && !dep[b[i].to]) {
                dep[b[i].to] = dep[now] + 1;
                if (b[i].to == T)
                    return 1;
                G.push(b[i].to);
            }
    }
    return 0;
}
/*
ll dfs(ll x, ll flo) {
        if(x == T) return flo;
        ll d = flo;
        for(ll i = crn[x]; i; i = b[i].next) {
                crn[x] = b[i].next;
                ll y = b[i].to;
                if(dep[y] == dep[x] + 1 && b[i].w > 0) {
                        ll tmp = dfs(y, min(d, b[i].w));
                        b[i].w -= tmp;
                        b[i ^ 1].w += tmp;
                        d -= tmp;
                        if(d == 0) break;
                }
        }
        return flo - d;
}
*/

ll dfs(int now, ll sum) {
    if (now == T)
        return sum;
    ll go = 0;
    for (int i = crn[now]; i; i = b[i].next)
        if (b[i].w && dep[now] + 1 == dep[b[i].to]) {
            ll this_go = dfs(b[i].to, min(sum - go, b[i].w));
            if (this_go) {
                b[i].w -= this_go;
                b[b[i].op].w += this_go;
                go += this_go;
                if (go == sum)
                    return go;
            }
        }
    dep[now] = -1;
    return go;
}

ll dinic() {
    ll ans = 0;
    while (bfs()) {
        ans += dfs(S, 1e18);
    }
    return ans;
}

void clean() {
    tot = 0;
    memset(head, 0, sizeof(head));
    memset(MB, 0, sizeof(MB));
    memset(b, 0, sizeof(b));
    memset(s, 0, sizeof(s));
}

int main() {
    freopen("variable.in", "r", stdin);
    freopen("variable.out", "w", stdout);
    scanf("%lld", &Q);
    while (Q--) {
        scanf("%lld%lld%lld%lld", &n, &w, &p, &q);
        for (ll i = 1; i <= n; i++) s[i] = 1;
        S = n + 1, T = n + 2;
        for (ll i = 1; i <= p; i++) {
            ll r1, r2, r3, r4, r5, r6, r7, r8, r9;
            scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld", &r1, &r2, &r3, &r4, &r5, &r6, &r7, &r8, &r9);
            MB[r1][r2] += r4;
            MB[r2][r3] += r5;
            MB[r3][r1] += r6;
            s[r1] += r7 - r9, s[r2] += r8 - r7, s[r3] += r9 - r8;
        }
        ll low = 0;
        for (ll i = 1; i <= n; i++) {
            low += abs(s[i]);
            if (s[i] > 0)
                add(S, i, 2 * s[i]);
            if (s[i] < 0)
                add(i, T, -2 * s[i]);
            for (int j = i + 1; j <= n; j++) {
                if (MB[i][j] + MB[j][i])
                    add(i, j, MB[i][j] * 2 + MB[j][i] * 2), add(j, i, MB[i][j] * 2 + MB[j][i] * 2);
            }
        }
        for (ll i = 1; i <= q; i++) {
            ll r1, r2, r3;
            scanf("%lld%lld%lld", &r1, &r2, &r3);
            if (r3 == 0)
                add(r2, r1, inf);
            if (r3 == 1)
                add(r1, r2, inf), add(r2, r1, inf);
            if (r3 == 2)
                add(S, r1, inf), add(r2, T, inf);
        }
        printf("%lld\n", dinic() * w - low * w);
        clean();
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liuziha/article/details/128815146

2017.3.38打卡 距省选10天-爱代码爱编程

嗯,又是一篇以嗯开头的牢骚。 之前去clyz集训,刚回来。大家都好强啊,我根本不能和他们比,说好的好好打暴力也还是弃疗和颓废的时候比较多。 回来第二天就来了学校,班里的同学都超欢迎我,我一进门他们还鼓掌庆祝我回来了(:з

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 9_xyz32768的博客-爱代码爱编程

找规律大法太好了! 题目 T1:BZOJ 2227 / ZJOI 2011 看电影 (movie)(组合数学+高精) T2:BZOJ 2660 / BeiJing WC 2012 最多的方案 (count)(找规律+递

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 10_xyz32768的博客-爱代码爱编程

一元n次方程求解,世界性难题上场,瞬间全懵。 题目 T1:BZOJ 2734 / HNOI 2012 集合选数 (set)(状压DP) T2:BZOJ 2302 / HAOI 2011 Problem c (c)(DP

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 11_xyz32768的博客-爱代码爱编程

重新认识了CDQ分治。 题目 T1:BZOJ 1857 / SCOI 2010 传送带 (walk)(三分) T2:BZOJ 1996 / HNOI 2010 合唱队 (chorus)(区间DP) T3:BZOJ 3

2021-07-27-爱代码爱编程

【2.4递归调用6262(流感传染)】第一次发文讲解,偏基础一点啦,毕竟我也是小白,不过是自己的解法也可以说是想法吧,,毕竟网络上搜到的解法好像没我的好呐,主要也是想分享一下我的见解 (抱着伊蕾娜酱打字呐,软软哒) 咱先介绍下自己吧,毕竟第一次发文。。。。。。 本人高一一枚,就读于fz clyz。。九月份就是高二了, 在这之前从没写过文章。。之后可能没

第十四届蓝桥杯集训——if——配套用法示例-爱代码爱编程

第十四届蓝桥杯集训——if——配套用法示例 目录 第十四届蓝桥杯集训——if——配套用法示例 方法1 方法2  其它指数幂   输入一个数n,判断n是否是2的指数。 n的取值范围(0=>n<=)​​​​ 题目看着很简单,其实在比较小的数上还是挺容易做的,但是依然要使用循环进行处理。 把这个数多次除以2, 如

【clyz集训】千与千寻【期望dp】【高斯消元】-爱代码爱编程

题目大意 给你一个n*m的平面,从(0,0)随机往上或右走。走到上边界时可以穿到最下边,到右边界时可以穿到最左边。问走到(x,y)的期望步数。 思路: 将左边界和下边界上的格子设为元,然后所有的格子的期望值都

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 8_xn训 练-爱代码爱编程

竟然卡SPFA,出题人好毒啊。 题目 T1:BZOJ 2330 / SCOI 2011 糖果 (candy)(差分约束) T2:BZOJ 2743 / HEOI 2012 采花 (flower)(离线+树状数组) T

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 5-爱代码爱编程

结论题真恶心。 题目 T1:BZOJ 2822 / AHOI 2012 树屋阶梯 (stair)(卡特兰数+高精) T2:BZOJ 2321 / BeiJing 集训 2011 星器 (star)(结论) T3:BZ

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 4-爱代码爱编程

图的边数范围竟然没有明显地给出,真不良心。 题目 T1:BZOJ 2815 / ZJOI 2012 灾难 (catas)(拓扑排序+LCA) T2:BZOJ 4069 / APIO 2015 巴厘岛的雕塑 (sculp

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 6-爱代码爱编程

LCT好强啊。 题目 T1:BZOJ 1004 / HNOI 2008 Cards (cards)(Burnside引理+DP) T2:BZOJ 2002 / HNOI 2010 弹飞绵羊 (bounce)(LCT)

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 1-爱代码爱编程

重新认识了Kruskal算法。 题目 T1:BZOJ 3293 / CQOI 2011 分金币 (coin)(乱搞???) T2:BZOJ 1007 / HNOI 2008 水平可见直线 (line)(栈维护凸壳)

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 7-爱代码爱编程

思维题真恶心。 题目 T1:BZOJ 1201 / HNOI 2005 数三角形 (triangle)(树状数组) T2:BZOJ 3624 / APIO 2008 免费道路 (roads)(思路+并查集) T3:B

[题解]clyz2018省选训(bao)练(zha)模拟赛 day 2-爱代码爱编程

初次见识了神奇的CDQ分治。 题目 T1:BZOJ 1093 / ZJOI 2007 最大半连通子图 (semi)(强连通分量+拓扑排序+DP) T2:BZOJ 1272 / BeiJing WC 2008 Gate