NOIP2020T1排水系统详细思路+题解

T1肯定是简单题，其它题没把握的情况下，花2小时也值得。此题不难，1小时应该能拿90分。
题目见洛谷7113
先看题，题目中也写了，没有环路，那么这就是个典型的有向无环图，从初始的接收口开始，依次向排出管道放水，一层一层放，某个中间节点先把来自爸爸、爷爷的水都接收完，再向下一级排出管道放水，很容易想到拓扑排序，按拓扑序依次给每个节点的儿子们放水即可。
观看输出要求，水量得保存到一个结构体里面

1、先把拓扑排序写对

#include <cstdio>
#define MAXN 10//此处为了调试方便，先开小一点，够样例2即可
using namespace std;
struct e{
    int to, nxt;
} es[MAXN*5+1];//存图，按题意，开节点个数5倍的数组即可
//下面cur和head用来链式前向星存图；rd保存节点入度，入度为0就是接水口；cd保存节点出度，出度为0就是题目要求输出的排出口；q是队列，用于拓扑排序
int cur, head[MAXN+1], rd[MAXN+1], cd[MAXN+1], q[MAXN+1];
int n, m;
//链式前向星存图加边函数
void addedge(int node, int to){
    es[++cur].to = to;
    es[cur].nxt = head[node];
    head[node] = cur;
}
//下面拓扑排序
void tsort(){
    int qi = 0, qj = 0;//队头队尾指针，队头指针指向实际元素，队尾指针指向队尾元素的下一个位置
    for(int i = 1; i <= n; i++){
        if (rd[i] == 0){
            q[qj++] = i;
        }
    }
    while(qi != qj){
        int node = q[qi++];
        for(int i = head[node]; i; i = es[i].nxt){
            rd[es[i].to]--;
            if (rd[es[i].to] == 0){
                q[qj++] = es[i].to;
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    int d, a;
    for(int i = 1; i <= n; i++){
        scanf("%d", &d);
        cd[i] = d;
        while(d--){
            scanf("%d", &a);
            addedge(i, a);
            rd[a]++;
        }
    }
    tsort();
    //拓扑排序以后，队列q里面的就是排好序的节点，序号[0, n)
    for(int i = 0; i < n; i++){
        printf("%d ", q[i]);
    }
    return 0;
}

上面代码存图，拓扑排序，有样例1输出拓扑序看一下写对没有。没问题就继续撸。

2、分水

存水量得用一个结构体，分别存放分子分母。然后重载+和/两个运算符，加用来加水，/用来平分水，发给儿子们。先别着急约分，输出结构手动约分和样例对比，没问题再加约分。

struct w{
    int p, q;
    w operator +(const w &r){
        w ret;
        if (q == 0){
            ret.q = r.q;
            ret.p = r.p;
        } else if (r.q == 0){
            ret.p = p;
            ret.q = q;
        } else {
            ret.q = q * r.q;
            ret.p = (p * r.q + q * r.p);
        }
        return ret;
    }
    w operator /(int x){
        w ret;
        ret.p = p;
        ret.q = q * x;
        return ret;
    }
} ws[MAXN+1];//顺便开数组，每个节点都有个元素存水量

加好以后，在原来拓扑排序找接水口的时候，给接水口赋值初始水量：

for(int i = 1; i <= n; i++){
        if (rd[i] == 0){
            q[qj++] = i;
            ws[i].p = ws[i].q = 1;//分子分母都是1
        }
    }

然后到拓扑排序的下面添加分水代码，从前到后依次分就行了

    //拓扑排序以后，队列q里面的就是排好序的节点，序号[0, n)
    //从前到后依次分水
    for(int i = 0; i < n; i++){
        int node = q[i];
        if(ws[node].p > 0){//有水
            w wc = ws[node] / cd[node];
            for(int j = head[node]; j; j = es[j].nxt){
                int to = es[j].to;
                ws[to] = ws[to] + wc;
            }
        }
    }

最后加上输出：

for(int i = 1; i <= n; i++){
        if (cd[i] == 0){
            printf("%d %d\n", ws[i].p, ws[i].q);
        }
    }

运行样例看一下，手动约分，没问题

3、约分

约分很好办，先求最大公约数gcd，然后都除以gcd。如何求最大公约数？2020年csp-s提高组初赛里就有，此处注意，2020csp提高组初赛有如何求最大公约数，2020csp提高组复赛有拓扑排序的题，所以考完csp以后，必须把真题全部吃透，在考noip的时候很有优势。

int gcd(int a, int b){
    if (b == 0) return a;
    return gcd(b, a % b);
}
struct w{
    int p, q;
    w operator +(const w &r){
        w ret;
        if (q == 0){
            ret.q = r.q;
            ret.p = r.p;
        } else if (r.q == 0){
            ret.p = p;
            ret.q = q;
        } else {
            ret.q = q * r.q;
            ret.p = (p * r.q + q * r.p);
        }
        if (p != 0){//约分
            int g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
    w operator /(int x){
        w ret;
        ret.p = p;
        ret.q = q * x;
        if (p != 0){
            int g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
} ws[MAXN+1];

加上约分，样例1和2都通过了，感觉很好，先把MAXN放大到最大的1e5,再运行样例3，发现大多数是对的，但有的不对，不用说肯定是爆int了，需要放大到unsigned long long，如果还爆就需要高精度了，考场来不及，就算了。

3+、官方数据放出后更新，先把分母乘起来，再约分就晚了

会爆unsign long long，90分变成60分，所以必须尽早约分，先算出分母的最小公倍数，使得中间结果尽量小，才不会爆ull。

ull gcd(ull a, ull b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

ull lcm(ull a, ull b){
    ull g = gcd(a, b);
    return (max(a, b) / g) * min(a, b);
}
struct w{
    ull p, q;
    w operator +(const w &r){
        w ret;
        if (q == 0){
            ret.q = r.q;
            ret.p = r.p;
        } else if (r.q == 0){
            ret.p = p;
            ret.q = q;
        } else {
            if (q % r.q == 0){
                ret.p = p + r.p * (q / r.q);
                ret.q = q;
            } else if (r.q % q == 0){
                ret.p = p * (r.q / q) + r.p;
                ret.q = r.q;
            } else {
                ull lm = lcm(q, r.q);
                ret.q = lm;
                ret.p = p * (lm / q) + r.p * (lm / r.q);
            }
        }
        if (p != 0){
            ull g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
    w operator /(int x){
        w ret;
        if (p % x == 0){
            ret.p = p / x;
            ret.q = q;
            return ret;
        }
        ret.p = p;
        ret.q = q * x;
        if (p != 0){
            ull g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
} ws[MAXN+1];

4、最终代码

#include <cstdio>
#include <algorithm>
#define MAXN 100000
typedef unsigned long long ull;
using namespace std;
ull gcd(ull a, ull b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

ull lcm(ull a, ull b){
    ull g = gcd(a, b);
    return (max(a, b) / g) * min(a, b);
}
struct w{
    ull p, q;
    w operator +(const w &r){
        w ret;
        if (q == 0){
            ret.q = r.q;
            ret.p = r.p;
        } else if (r.q == 0){
            ret.p = p;
            ret.q = q;
        } else {
            if (q % r.q == 0){
                ret.p = p + r.p * (q / r.q);
                ret.q = q;
            } else if (r.q % q == 0){
                ret.p = p * (r.q / q) + r.p;
                ret.q = r.q;
            } else {
                ull lm = lcm(q, r.q);
                ret.q = lm;
                ret.p = p * (lm / q) + r.p * (lm / r.q);
            }
        }
        if (p != 0){
            ull g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
    w operator /(int x){
        w ret;
        if (p % x == 0){
            ret.p = p / x;
            ret.q = q;
            return ret;
        }
        ret.p = p;
        ret.q = q * x;
        if (p != 0){
            ull g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
} ws[MAXN+1];

struct e{
    int to, nxt;
} es[MAXN*5+1];//存图，按题意，开节点个数5倍的数组即可
//下面cur和head用来链式前向星存图；rd保存节点入度，入度为0就是接水口；cd保存节点出度，出度为0就是题目要求输出的排出口；q是队列，用于拓扑排序
int cur, head[MAXN+1], rd[MAXN+1], cd[MAXN+1], q[MAXN+1];
int n, m;
void addedge(int node, int to){
    es[++cur].to = to;
    es[cur].nxt = head[node];
    head[node] = cur;
}
//下面拓扑排序
void tsort(){
    int qi = 0, qj = 0;
    for(int i = 1; i <= n; i++){
        if (rd[i] == 0){
            q[qj++] = i;
            ws[i].p = ws[i].q = 1;
        }
    }
    while(qi != qj){
        int node = q[qi++];
        for(int i = head[node]; i; i = es[i].nxt){
            rd[es[i].to]--;
            if (rd[es[i].to] == 0){
                q[qj++] = es[i].to;
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    int d, a;
    for(int i = 1; i <= n; i++){
        scanf("%d", &d);
        cd[i] = d;
        while(d--){
            scanf("%d", &a);
            addedge(i, a);
            rd[a]++;
        }
    }
    tsort();
    //拓扑排序以后，队列q里面的就是排好序的节点，序号[0, n)
    //从前到后依次分水
    for(int i = 0; i < n; i++){
        int node = q[i];
        if(ws[node].p > 0 && cd[node] > 0){//有水
            w wc = ws[node] / cd[node];
            for(int j = head[node]; j; j = es[j].nxt){
                int to = es[j].to;
                ws[to] = ws[to] + wc;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if (cd[i] == 0){
            printf("%llu %llu\n", ws[i].p, ws[i].q);
        }
    }

    return 0;
}

5、深搜

写完拓扑排序才发现，直接深搜也可以，更简单......

#include <cstdio>
#define MAXN 100000
typedef __int128_t ull;
using namespace std;
ull gcd(ull a, ull b){
    return b == 0 ? a : gcd(b, a % b);
}
struct w{
    ull p, q;
    w operator +(const w &r){
        w ret;
        if (q == 0){
            ret.q = r.q;
            ret.p = r.p;
        } else if (r.q == 0){
            ret.p = p;
            ret.q = q;
        } else {
            ret.q = q * r.q;
            ret.p = (p * r.q + q * r.p);
        }
        if (p != 0){
            ull g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
    w operator /(int x){
        w ret;
        if (p % x == 0){
            ret.p = p / x;
            ret.q = q;
            return ret;
        }
        ret.p = p;
        ret.q = q * x;
        if (p != 0){
            ull g = gcd(ret.p, ret.q);
            ret.p /= g;
            ret.q /= g;
        }
        return ret;
    }
} ws[MAXN+1];

struct e{
    int to, nxt;
} es[MAXN*5+1];//存图，按题意，开节点个数5倍的数组即可
//下面cur和head用来链式前向星存图；rd保存节点入度，入度为0就是接水口, cd保存节点出度。
int cur, head[MAXN+1], rd[MAXN+1], cd[MAXN+1];
int n, m;
void addedge(int node, int to){
    es[++cur].to = to;
    es[cur].nxt = head[node];
    head[node] = cur;
}
//深搜，有向没有环，和树差不多，不用考虑太多,x表示要搜的节点，add表示加的水量
void dfs(int x, w add){
    if(head[x] == 0){
        ws[x] = ws[x] + add;
        return;
    }

    w wc = add / cd[x];
    for(int j = head[x]; j; j = es[j].nxt){
        dfs(es[j].to, wc);
    }
}

void p128(ull x){
    if(x > 9)
        p128(x / 10);
    printf("%d", x % 10);
}

int main(){
    // freopen("water.in", "r", stdin);
    // freopen("water.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int d, a;
    for(int i = 1; i <= n; i++){
        scanf("%d", &d);
        cd[i] = d;
        while(d--){
            scanf("%d", &a);
            addedge(i, a);
            rd[a]++;
        }
    }

    w wc;
    wc.p = wc.q = 1;
    for(int i = 1; i <= m; i++){
        dfs(i, wc);
    }
    for(int i = 1; i <= n; i++){
        if (head[i] == 0){
            p128(ws[i].p);
            printf(" ");
            p128(ws[i].q);
            printf("\n");
        }
    }
    return 0;
}

最后编辑于：2020.12.10 20:44:16

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,602评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,442评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,878评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,306评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,330评论 5赞 373
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,071评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,382评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,006评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,512评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,965评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,094评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,732评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,283评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,286评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,512评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,536评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,828评论 2赞 345