作者： KSkun

2018年4月25日

[WC2007]剪刀石头布题解

题目地址：&#279 …

题解, 算法, NOI系列

by KSkun

0 Comments

2018年4月24日

[JSOI2009]球队收益题解

题目地址：&#279 …

题解, 省选, 算法

by KSkun

0 Comments

2018年4月24日

4月21日

早上回了学校，然后发现机房里还有化竞的在前面各种颓。简单跟同学处理了一下前几天的模拟考，然后被这股风气带的完全无法写题。颓爆。
我们往定员7人的车里塞了8个人，挤爆。
到了西安接上预谋已久的HDMI线，宾馆电视拿来当第二屏幕用，爽爆，下面是效果图。

晚上出去逛了一圈，晚饭吃的相当不错ww（美食文章？？？）

睡的比较晚，被一个GCJ的题卡了（实际上就是上一篇文章）。最大流转最小割转最短路的转化思想，最开始写的求两个矩形的最短路的方法WA了，后来写最大流暴力又WA了，手玩数据太慢了，被逼无奈google了一发结果还真找到了能用的程序，借鉴了一发算法然后写了个Floyd测试，小数据AC。Floyd跑大数据太慢了，又困得不行，于是干脆先睡觉，明天再改。
同房间的哥们肝了一晚上崩崩崩+FGO。

4月22日

起晚了。肉夹馍好好吃ww（美食文章√）

把Floyd改了SPFA，大数据还是要跑个一会。不过还好成功AC了，赶紧把题解文章写了。
早上颓爆，用电视看番。碰到了老班探望，听说化学题特别尴尬，像考政治一样。其实好久没回学校碰见老班这个就是很尴尬的事情emm
我用HDMI接电视用的操作震惊了老师2333333
同学表示很虚，因为他们之前的模拟赛考出阴影来了。我当时还觉得比较稳。（flag）
A，考会不会写C++，无压力1A。
B，好像是个推结论题，试着玩了一下样例结果并没发现什么大结论，决定先跳。
C，以前写过的找规律题，打了个小表发现了点规律不过好麻烦，跳了跳了。
D，烂大街的经典贪心模型，直接打了1A。
E，模拟，写写写，1A。
F，字符串匹配+计数，呜哇，好麻烦，跳了跳了。
G，BFS统计连通块，写写写，WAWA。手玩+肉眼调试并未发现不妥于是跳。
H，模拟，写写写，WAWA。同G。
回到了G，把样例魔改了一下发现WA了，赶紧调好交上去，AC。
回到了H，改样例对结果并未造成任何影响，GG。扔了。
C，用刚刚打表的结论写了个程序交上去，1A。
F，哇好麻烦还剩20分钟写不完的。
开始研究B，勉强研究出了写法，写写写，考试结束了还是没写完GG。
最后只A了5题，事后才知道F题有很简单的写法，亏大了QAQ
心态有点崩，已经这么拼命了，在这种简单考试的时候还会崩的如此厉害。何况那个rk1的选手全1A还只用了1小时20分钟。

4月23日

没有动力继续下去了。想把自己的费用流朴素EK改的好看一点的，但是刚开始就放弃了。
找到了一部叫《比宇宙还远的地方》的励志番，看了第一集就决定今天看完。
看完了。很现实的番。仿佛找到了自己的影子。
半夜写完了这篇文章，然后困成SB。还想写写影评之类的呢。总之算是回复了一点动力吧。
选项一直都有，但是我们选择了这里。

日常, 算法, 随笔

by KSkun

0 Comments

2018年4月22日

[GCJ2014R2]Don’t Break The Nile 题解

题目地址：Googl …

题解, 算法, 其他

by KSkun

0 Comments

2018年4月21日

[NOI2010]海拔题解

题目地址：&#279 …

题解, 算法, NOI系列

by KSkun

0 Comments

2018年4月20日

[BJOI2006]狼抓兔子题解

题目地址：洛谷：【P4001】[BJOI2006]狼抓兔子 – 洛谷、BZOJ：Problem 1001. — [BeiJing2006]狼抓兔子

题目描述

现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为(1,1),右下角点为(N,M)(上图中N=3,M=4).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下角(N,M)的窝中去，狼王开始伏击这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。

输入输出格式

输入格式：
第一行为N,M.表示网格的大小，N,M均小于等于1000.
接下来分三部分
第一部分共N行，每行M-1个数，表示横向道路的权值.
第二部分共N-1行，每行M个数，表示纵向道路的权值.
第三部分共N-1行，每行M-1个数，表示斜向道路的权值.

输出格式：
输出一个整数，表示参与伏击的狼的最小数量.

输入输出样例

输入样例#1：

输出样例#1：

题解

网络流

我们可以直接按照图示建立网络，求最小割。Dinic跑是很快的。

对偶图

这有个讲解对偶图的ppt：点击下载
然后我们可以利用对偶图的性质，建立对偶图，求S到T的最短路，即为最小割。这样来做点数边数能够变小，避免了空间爆炸的情况。
下面的代码中，建图的规律是第一行右上三角形的编号为1~m-1，左下三角形的编号为m~2m-2，底下以此类推。需要判断越界的面属于S还是T。

代码

网络流

// Code by KSkun, 2018/4
#include <cstdio>
#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(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 2000005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN * 5];
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, cap, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    level[s] = 0; que.push(s);
    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(level[v] == -1 && gra[i].cap > 0) {
                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 <= 0) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                flow += d; left -= d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(left <= 0) 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, t;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < m; j++) {
            t = readint();
            addedge((i - 1) * m + j, (i - 1) * m + j + 1, t);
        }
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= m; j++) {
            t = readint();
            addedge((i - 1) * m + j, i * m + j, t);
        }
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < m; j++) {
            t = readint();
            addedge((i - 1) * m + j, i * m + j + 1, t);
        }
    }
    printf("%d", dinic(1, n * m));
    return 0;
}

对偶图

参考资料：【BJOI2006】狼抓兔子 – flow丶 – 博客园

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

#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(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 2000005, INF = 1e9;

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

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

int dis[MAXN];
bool inque[MAXN];

inline void spfa(int s) {
    std::queue<int> que;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; 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(dis[v] > dis[u] + gra[i].w) {
                dis[v] = dis[u] + gra[i].w;
                if(!inque[v]) {
                    inque[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

int n, m, t, S, T;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); 
    S = 0; T = (n - 1) * (m - 1) * 2 + 1;
    int u = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < m; j++) {
            t = readint();
            int v = u - (m - 1), u1 = u, v1 = v;
            if(v <= S) v1 = S;
            if(u >= T) u1 = T;
            addedge(u1, v1, t);
            u++;
        }
        u += m - 1;
    }
    u = m;
    for(int i = 1; i < n; i++) {
        for(int j = 1; j <= m; j++) {
            t = readint();
            int v = u - m, u1 = u, v1 = v;
            if(v <= 2 * (i - 1) * (m - 1)) v1 = T;
            if(u > 2 * i * (m - 1)) u1 = S; 
            addedge(u1, v1, t);
            u++;
        }
        u += m - 2;
    }
    u = 1;
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < m; j++) {
            t = readint();
            addedge(u, u + m - 1, t);
            u++;
        }
        u += m - 1;
    }
    spfa(S);
    printf("%d", dis[T]);
    return 0;
}

题解, 算法, 省选

by KSkun

0 Comments

2018年4月19日

[CF311E]Biologist 题解

题目地址：Codef …

题解, 算法, Codeforces

by KSkun

0 Comments

2018年4月19日

[CEOI2008]Order 题解

题目地址：BZOJ& …

题解, 算法, 其他

by KSkun

0 Comments

2018年4月19日

[NOI2006]最大获利题解

题目地址：洛谷：【P4174】[NOI2006]最大获利 – 洛谷、BZOJ：Problem 1497. — [NOI2006]最大获利

题目描述

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i个通讯中转站需要的成本为 Pi（1≤i≤N）。
另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为 Ai, Bi和 Ci：这些用户会使用中转站 Ai 和中转站 Bi 进行通讯，公司可以获益 Ci。（1≤i≤M, 1≤Ai,Bi≤N）
THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

输入输出格式

输入格式：
输入文件中第一行有两个正整数 N 和 M 。
第二行中有 N 个整数描述每一个通讯中转站的建立成本，依次为 P1,P2,…,PN。
以下 M 行，第(i + 2)行的三个数 Ai,Bi和 Ci描述第 i 个用户群的信息。
所有变量的含义可以参见题目描述。

输出格式：
你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

输入输出样例

输入样例#1：

输出样例#1：

说明

样例：选择建立 1、2、3 号中转站，则需要投入成本 6，获利为 10，因此得到最大收益 4。
100%的数据中：N≤5 000，M≤50 000，0≤ Ci ≤100，0≤ Pi ≤100。

题解

这类问题有一个统一的模型，叫最大权闭合子图。
我们把中转站向汇连边，容量为建设成本。把客户向源连边，容量为获利。再把客户和用到的中转站之间连边，容量无限。求一次最小割，然后用所有获利减去这个最小割的权值和即为答案。
最小割肯定不会去割中间容量无限的边，因此割的是与源汇相连的边。割掉客户与源相连的边的含义是不要这个客户了，割掉中转站与汇相连的边的含义是不建这个中转站了。因此最小割的含义是发展客户净利润为负的收益加上建设中转站的总成本，也就是损失的收益+建设的开支，直接用总收益减去它就是答案。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#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(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 3];
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;
    level[s] = 0; que.push(s);
    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(level[v] == -1 && gra[i].cap > 0) {
                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 <= 0) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(left <= 0) {
                    //level[u] = -1; 不注释掉会TLE
                    return flow;
                }
            }
        }
    }
    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, pi, ai, bi, ci, S, T, ans;

// 1 ~ n device
// n+1 ~ n+m custom

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        pi = readint();
        addedge(i, T, pi);
    }
    for(int i = 1; i <= m; i++) {
        ai = readint(); bi = readint(); ci = readint();
        ans += ci;
        addedge(S, n + i, ci);
        addedge(n + i, ai, INF);
        addedge(n + i, bi, INF);
    }
    ans -= dinic(S, T);
    printf("%d", ans);
    return 0;
}

题解, 算法, NOI系列

by KSkun

0 Comments

2018年4月18日

[BZOJ2561]最小生成树题解

题目地址：BZOJ& …

题解, 算法, BZOJ

by KSkun

0 Comments