标签：最大流

如果我们把棋盘上看做只有黑色棋子，那么可以把交换达到目标状态看做把每个黑色棋子移动到目标位置上去。在移动的过程中，起终点格子各参与一次交换，路径上的其他格子各参与两次交换。既然如此，我们可以把次数上限平分成向上一步交换和向下一步交换两部分。
建图的时候，把每个格子拆成三个点，入点、原点、出点，流的方向应该是入点→原点→出点，这三个点之间的边，容量均为次数上限的一半，不妨把交换次数（费用）放在入点→原点的边上，可以避免算多交换次数。
对于初始状态的黑点格子，从源向该格子的原点连容量1费用0的边，对于目标状态的黑点格子，从该格子的原点向汇连容量1费用0的边，对于有公共点/边的格子，从出点向入点连容量无限费用0的边。至此网络就建立完成了，只需要跑最小费用最大流，若满流则答案为费用，否则无解。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline int readdigit() {
    char c;
    while(!isdigit(c = fgc())) {}
    return c - '0';
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 4];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap && dis[v] > dis[u] + gra[i].cost) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(f[u], gra[i].cap);
                pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    que.push(v); inque[v] = true;
                }
            }
        }
    }
    return f[t];
}

int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        flow += f[t]; cost += f[t] * dis[t];
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t]; gra[pree[i] ^ 1].cap += f[t];
        }
    }
}

const int fix[][8] = {{-1, 1, -1, 1, -1, 1, 0, 0}, {0, 0, -1, 1, 1, -1, -1, 1}};

int n, m, cnt, st[25][25], ed[25][25], lim[25][25], S, T;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); S = n * m * 3 + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            st[i][j] = readdigit();
            if(st[i][j]) cnt++;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ed[i][j] = readdigit();
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            lim[i][j] = readdigit();
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(st[i][j]) addedge(S, (i - 1) * m + j, 1, 0);
            if(ed[i][j]) addedge((i - 1) * m + j, T, 1, 0);
            if(st[i][j] && !ed[i][j]) {
                addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, lim[i][j] / 2, 1);
                addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, (lim[i][j] + 1) / 2, 0);
            } else if(!st[i][j] && ed[i][j]) {
                addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, (lim[i][j] + 1) / 2, 1);
                addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, lim[i][j] / 2, 0);
            } else {
                addedge(n * m + (i - 1) * m + j, (i - 1) * m + j, lim[i][j] / 2, 1);
                addedge((i - 1) * m + j, n * m * 2 + (i - 1) * m + j, lim[i][j] / 2, 0);
            }
            for(int k = 0; k < 8; k++) {
                int nx = i + fix[0][k], ny = j + fix[1][k];
                if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                addedge(n * m * 2 + (i - 1) * m + j, n * m + (nx - 1) * m + ny, INF, 0);
            }
        }
    }
    mcmf(S, T);
    printf("%d", flow >= cnt ? cost : -1);
    return 0;
}

题解, 省选, 算法

by KSkun

0 Comments

2018年6月10日

[BZOJ3438]小M的作物题解

题目地址：洛谷：【P1361】小M的作物 – 洛谷、BZOJ：Problem …

题解, 算法, BZOJ

by KSkun

0 Comments

2018年6月9日

[CQOI2014]危桥题解

题目地址：洛谷：【P3163】[CQOI2014]危桥 – 洛谷、BZOJ：P …

题解, 省选, 算法

by KSkun

0 Comments

2018年6月5日

[JSOI2010]冷冻波题解

题目地址：洛谷：【P4048】[JSOI2010]冷冻波 – 洛谷、BZOJ：Problem 1822. — [JSOI2010]Frozen Nova 冷冻波

题目描述

WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。
在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。
现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？

题意简述

巫妖一次可以杀死一只圆形范围内且连线与树障（圆形区域）无公共点的精灵，但是攻击有CD。求至少花费多少时间可以杀死全部精灵。

输入输出格式

输入格式：
输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。
接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。
再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。
再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。
输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。

输出格式：
输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。

输入输出样例

输入样例#1：

2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

输出样例#1：

题解

首先我们可以处理出来每个巫妖可以杀死哪些精灵，简单的实现就是判断距离是否超过以及是否跟某个树有交点。这里判交点用的方法是检查端点及叉积计算出圆心-直线距离再判断是否有交点。
得到了这个表以后，我们就可以二分答案，每次使用最大流检验，建立源→巫妖→精灵→汇的网络，巫妖→精灵→汇中间的所有边容量为1，源→巫妖的所有边容量为floor(答案/该巫妖CD)+1，代表这一次该巫妖最多杀死多少精灵。满流即代表答案可行。
复杂度玄学。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1005, INF = 1e9;
const double EPS = 1e-8;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 8];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    que.push(s); level[s] = 0;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap && level[v] == -1) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(level[v] == level[u] + 1 && gra[i].cap) {
            int f = dfs(v, t, std::min(left, gra[i].cap));
            if(f) {
                flow += f; left -= f;
                gra[i].cap -= f; gra[i ^ 1].cap += f;
                if(!left) break;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) flow += f;
    }
    return flow;
}

int n, m, k, S, T;
std::vector<int> elfs[MAXN];

class Pos {
public:
    int x, y;
    Pos() {}
    Pos(int x, int y): x(x), y(y) {}
};

class Litch : public Pos {
public:
    int r, t;
} lit[MAXN];

typedef Pos Elf;

Elf elf[MAXN];

class Tree : public Pos {
public:
    int r;
} tre[MAXN];

inline double dis(Pos x, Pos y) {
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}

inline bool inter(Pos x, Pos y, Tree tr) {
    double dis1 = dis(x, tr), dis2 = dis(y, tr), dis3 = dis(x, y);
    if(dis1 - tr.r < EPS || dis2 - tr.r < EPS) return true;
    double dis4 = fabs((x.x - y.x) * (x.y - tr.y) - (x.y - y.y) * (x.x - tr.x)) / dis3;
    double dis5 = sqrt(dis1 * dis1 - dis4 * dis4), dis6 = sqrt(dis2 * dis2 - dis4 * dis4);
    return dis5 + dis6 - dis3 < EPS && dis4 - tr.r < EPS;
}

inline bool check(int x) {
    tot = 0; memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; i++) {
        addedge(S, i, x / lit[i].t + 1);
        for(int j = 0; j < elfs[i].size(); j++) {
            addedge(i, elfs[i][j] + n, 1);
        }
    }
    for(int i = 1; i <= m; i++) {
        addedge(i + n, T, 1);
    }
    return dinic(S, T) >= m;
}

int main() {
    n = readint(); m = readint(); k = readint(); S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        lit[i].x = readint(); lit[i].y = readint(); lit[i].r = readint(); lit[i].t = readint();
    }
    for(int i = 1; i <= m; i++) {
        elf[i].x = readint(); elf[i].y = readint();
    }
    for(int i = 1; i <= k; i++) {
        tre[i].x = readint(); tre[i].y = readint(); tre[i].r = readint();
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(dis(lit[i], elf[j]) - lit[i].r > EPS) continue;
            bool success = true;
            for(int jj = 1; jj <= k; jj++) {
                if(inter(lit[i], elf[j], tre[jj])) {
                    success = false; break;
                }
            }
            if(success) elfs[i].push_back(j);
        }
    }
    int l = 0, r = INF, mid;
    if(check(0)) {
        printf("0"); return 0;
    }
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid; else l = mid;
    }
    printf("%d", r == INF ? -1 : r);
    return 0;
}

题解, 省选, 算法

by KSkun

0 Comments

2018年6月5日

[POI2005]KOS-Dicing 题解

题目地址：洛谷：【P3425】[POI2005]KOS-Dicing – 洛谷 …

题解, 算法, 其他

by KSkun

0 Comments

2018年5月9日

[NOI2012]美食节题解

题目地址：洛谷：【P2050】[NOI2012]美食节 – 洛谷、BZOJ：P …

题解, 算法, NOI系列

by KSkun

0 Comments

2018年5月8日

[ZJOI2010]网络扩容题解

题目地址：洛谷：【P2604】[ZJOI2010]网络扩容 – 洛谷、BZOJ：Problem 1834. — [ZJOI2010]network 网络扩容

题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、在不扩容的情况下，1到N的最大流； 2、将1到N的最大流增加K所需的最小扩容费用。

输入输出格式

输入格式：
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

输出格式：
输出文件一行包含两个整数，分别表示问题1和问题2的答案。

输入输出样例

输入样例#1：

输出样例#1：

13 19

说明

30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10

题解

对于问题1，其实可以单独拿出来跑最大流，考虑问题2。我们在建边的时候建两种边，一种容量为c，费用为0，一种容量无限，费用为w，这样就可以实现扩容付费了。实际上问题2和问题1可以合在一起做，先跑一遍MCMF，注意当即将产生费用的时候终止，输出产生费用前的最大流，然后从源向1连边容量k费用0用于限制流量，从新源跑MCMF，可以将之前的残量网络利用起来避免重复跑MCMF。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int n, m, k;

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(gra[i].cap, f[u]);
                pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
    return f[t] != 0;
}

int flow, cost;

inline void mcmf(int s, int t, bool flag) {
    while(spfa(s, t)) {
        if(flag && dis[t]) break;
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
        }
        flow += f[t]; cost += dis[t] * f[t];
    }
}

int u, v, c, w;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); k = readint();
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint(); c = readint(); w = readint();
        addedge(u, v, c, 0);
        addedge(u, v, k, w);
    }
    mcmf(1, n, true);
    printf("%d ", flow);
    addedge(0, 1, k, 0);
    mcmf(0, n, false);
    printf("%d", cost);
    return 0;
}

题解, 省选, 算法

by KSkun

0 Comments

2018年5月8日

[SDOI2009]晨跑题解

题目地址：洛谷：【P2153】[SDOI2009]晨跑 – 洛谷、BZOJ：P …

题解, 省选, 算法

by KSkun

0 Comments

标签： 最大流

题目描述

输入输出格式

输入输出样例

题解

代码

题目描述

题意简述

输入输出格式

输入输出样例

题解

代码

题目描述

输入输出格式

输入输出样例

说明

题解

代码

标签：最大流