月度归档: 2018 年 5 月

[SCOI2005]骑士精神 题解

[SCOI2005]骑士精神 题解

题目地址:洛谷:【P2324】[SCOI2005]骑士精神 – 洛谷、BZOJ 

[洛谷1901]发射站 题解

[洛谷1901]发射站 题解

题目地址:洛谷:【P1901】发射站 – 洛谷 题目描述 某地有 N 个能量发 

[ZJOI2006]物流运输 题解

[ZJOI2006]物流运输 题解

题目地址:洛谷:【P1772】[ZJOI2006]物流运输 – 洛谷、BZOJ:Problem 1003. — [ZJOI2006]物流运输

题目描述

物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。

输入输出格式

输入格式:
物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。

输出格式:
包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

输入输出样例

输入样例#1:

5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5

输出样例#1:

32

题解

n和m非常小,尤其是m,所以可以乱搞。我们考虑预处理出一个数组dist[i][j]表示时间段[i, j]内不修改路线的最短路,这个预处理可以[eq]O(n^2)[/eq]枚举时间段每次判断该时间段内哪些点始终可用,并且跑一遍SPFA。后面就是DP,每次的决策是在何处改线路,dp[i]表示时间段[1, i]最小开销,枚举一个j<i,表示在j时间处改变路线,转移如下
\displaystyle dp[i] = \min\{dist[1][i], \min\{dp[j]+k+dist[j+1][i] \cdot (i-j)\}\}
答案即为dp[n]。

代码

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

#include <vector>
#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 = 105;

struct Edge {
    int to, w;
};

std::vector<Edge> gra[MAXN];

int n, m, k, e, d;

int dis[MAXN];
bool del[MAXN][MAXN], ndel[MAXN], inque[MAXN];
std::queue<int> que;

inline int spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(ndel, 0, sizeof(ndel));
    for(int i = 1; i <= m; i++) {
        for(int j = s; j <= t; j++) {
            if(del[i][j]) {
                ndel[i] = true; break;
            }
        }
    }
    dis[1] = 0; inque[1] = true; que.push(1);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i].to;
            if(ndel[v]) continue;
            if(dis[v] > dis[u] + gra[u][i].w) {
                dis[v] = dis[u] + gra[u][i].w;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
    return dis[m];
}

int dist[MAXN][MAXN];
LL dp[MAXN];

int main() {
    n = readint(); m = readint(); k = readint(); e = readint();
    for(int i = 1, u, v, w; i <= e; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u].push_back(Edge {v, w});
        gra[v].push_back(Edge {u, w});
    }
    d = readint();
    for(int i = 1, u, a, b; i <= d; i++) {
        u = readint(); a = readint(); b = readint();
        for(int j = a; j <= b; j++) {
            del[u][j] = true;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            dist[i][j] = spfa(i, j);
        }
    }
    for(int i = 1; i <= n; i++) {
        dp[i] = 1ll * dist[1][i] * i;
        for(int j = 1; j < i; j++) {
            dp[i] = std::min(dp[i], dp[j] + k + 1ll * dist[j + 1][i] * (i - j));
        }
    }
    printf("%lld", dp[n]);
    return 0;
}
[USACO09FEB]改造路Revamping Trails 题解

[USACO09FEB]改造路Revamping Trails 题解

题目地址:洛谷:【P2939】[USACO09FEB]改造路Revamping Trail 

[NOIP2012提高]开车旅行 题解

[NOIP2012提高]开车旅行 题解

题目地址:洛谷:【P1081】开车旅行 – 洛谷 题目描述 小 A 和小 B  

[USACO5.3]校园网Network of Schools 题解

[USACO5.3]校园网Network of Schools 题解

题目地址:洛谷:【P2746】[USACO5.3]校园网Network of Schools – 洛谷

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A 也不一定在 B 学校的列表中。
你要写一个程序计算,根据协议,为了让网络中所有的学校都用上新软件,必须接受新软件副本的最少学校数目(子任务 A)。更进一步,我们想要确定通过给任意一个学校发送新软件,这个软件就会分发到网络中的所有学校。为了完成这个任务,我们可能必须扩展接收学校列表,使其加入新成员。计算最少需要增加几个扩展,使得不论我们给哪个学校发送新软件,它都会到达其余所有的学校(子任务 B)。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

输入输出格式

输入格式:
输入文件的第一行包括一个整数 N:网络中的学校数目(2 <= N <= 100)。学校用前 N 个正整数标识。
接下来 N 行中每行都表示一个接收学校列表(分发列表)。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

输出格式:
你的程序应该在输出文件中输出两行。
第一行应该包括一个正整数:子任务 A 的解。
第二行应该包括子任务 B 的解。

输入输出样例

输入样例#1:

5
2 4 3 0
4 5 0
0
0
1 0

输出样例#1:

1
2

题解

由于强连通分量内部的点两两互达,不需要考虑内部的情况,直接缩点。对于子任务A,答案就是缩点后入度为0的点的数量,因为当所有入度为0的点都被分发了,入度大于0的点也会被分发,反过来说,如果只分发给入度大于0的点,入度为0的点永远不会被分发到。对于子任务B,考虑只需要从出度为0的点向入度为0的点连边即可,因此答案是出度为0的点的数量和入度为0的点的数量的较大值。

代码

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

#include <algorithm>
#include <vector>
#include <stack>

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 = 105;

int n, m;

std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], sno[MAXN], scc, clk;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    insta[u] = true; sta.push(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        scc++;
        int p;
        do {
            p = sta.top(); sta.pop(); insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

int ind[MAXN], outd[MAXN];

int v;

int main() {
    n = readint();
    for(int u = 1; u <= n; u++) {
        for(;;) {
            v = readint(); if(!v) break;
            gra[u].push_back(v);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++) {
        for(int i = 0; i < gra[u].size(); i++) {
            int v = gra[u][i];
            if(sno[u] != sno[v]) {
                outd[sno[u]]++;
                ind[sno[v]]++;
            }
        }
    }
    if(scc == 1) {
        puts("1\n0");
        return 0;
    }
    int out0 = 0, in0 = 0;
    for(int i = 1; i <= scc; i++) {
        if(!ind[i]) in0++;
        if(!outd[i]) out0++;
    }
    printf("%d\n%d", in0, std::max(out0, in0));
    return 0;
}
[APIO2017]商旅 题解

[APIO2017]商旅 题解

题目地址:洛谷:【P3778】[APIO2017]商旅 – 洛谷、BZOJ:P 

[POI2008]BLO-Blockade 题解

[POI2008]BLO-Blockade 题解

题目地址:洛谷:【P3469】[POI2008]BLO-Blockade –  

[HNOI2012]矿场搭建 题解

[HNOI2012]矿场搭建 题解

题目地址:洛谷:【P3225】[HNOI2012]矿场搭建 – 洛谷、BZOJ:Problem 2730. — [HNOI2012]矿场搭建

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

输入输出格式

输入格式:
输入文件有若干组数据,每组数据的第一行是一个正整数 N(N<=500),表示工地的隧道数,接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

输出格式:
输入文件中有多少组数据,输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与:之间无空格,: 之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

输入输出样例

输入样例#1:

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

输出样例#1:

Case 1: 2 4
Case 2: 4 1

说明

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6);
Case 2 的一组解为(4,5,6,7)。

题解

我们考虑每个点双连通分量。一个点双中如果有不小于2个割点,就算一个割点坍塌,仍然可以通过另一个割点前往其他点双找救援出口;如果只有一个割点,那么割点坍塌了就不行了,需要找一个不是割点的点设置出口;如果没有割点,需要设置两个出口,因为万一一个塌了可以去另一个。
那么我们只需要处理一遍割点,然后DFS统计每个点双不包含割点在内的大小及割点数量,并统计出答案即可。

代码

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

#include <algorithm>
#include <vector>

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 = 10005;

int n, m;

std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], clk;
bool cut[MAXN];

inline void tarjan(int u, int fa) {
    int ch = 0;
    dfn[u] = low[u] = ++clk;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            ch++; tarjan(v, u);
            low[u] = std::min(low[u], low[v]);
            if(low[v] >= dfn[u]) cut[u] = true;
        } else if(dfn[v] < dfn[u] && v != fa) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(ch == 1 && !fa) cut[u] = false;
}

int ccnt, siz, vis[MAXN], dclk;

inline void dfs(int u) {
    vis[u] = dclk; siz++;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] != dclk && cut[v]) {
            ccnt++; vis[v] = dclk;
        }
        if(!vis[v] && !cut[v]) dfs(v);
    }
}

int u, v;

int main() {
    for(int kase = 1;; kase++) {
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(cut, 0, sizeof(cut));
        memset(vis, 0, sizeof(vis));
        n = clk = dclk = 0;
        m = readint(); if(!m) break;
        for(int i = 1; i < MAXN; i++) gra[i].clear();
        for(int i = 1; i <= m; i++) {
            u = readint(); v = readint();
            gra[u].push_back(v);
            gra[v].push_back(u);
            n = std::max(n, std::max(u, v));
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) tarjan(i, 0);
        }
        int ans1 = 0;
        LL ans2 = 1;
        for(int i = 1; i <= n; i++) {
            if(!vis[i] && !cut[i]) {
                dclk++; ccnt = siz = 0;
                dfs(i);
                if(!ccnt) {
                    ans1 += 2;
                    ans2 *= 1ll * siz * (siz - 1) / 2;
                } else if(ccnt == 1) {
                    ans1++;
                    ans2 *= siz;
                }
            }
        }
        printf("Case %d: %d %lld\n", kase, ans1, ans2);
    }
    return 0;
}
[HAOI2006]受欢迎的牛 题解

[HAOI2006]受欢迎的牛 题解

题目地址:洛谷:【P2341】[HAOI2006]受欢迎的牛 – 洛谷、BZO