P7177 [COCI2014-2015#4] MRAVI题解

· · 题解

这道题是我随机跳题跳到的，没什么技术含量却卡了我整整一个下午，发篇题解纪念一下，另外这是本人第一次发题解，如有问题还请指出。

Part1 思路

首先我们很容易就能看出每个叶子节点能收到的液体和倒入的液体是成正比的，答案满足所谓单调性，那么就可以用二分答案来求解。

大体思路很简单，可是 check 函数怎么写呢？

我们可以使用 DFS，把每个叶子节点能获得的液体求出来，再和 k_i 做比较，就可以了。

Part2 代码实现

2-1 前置工作

我们首先要存树，我这里用的是链式前向星，不过多讲解，直接上代码（该开 double 记得开）：

struct edge
{
    int to, pre, opt;//opt表示是否是超级管道 
    double dis;//边权，即题中的流量 
}e[maxn << 1];//因为不知道父子关系，所以要存双向边,开二倍数组
int head[maxn], cnt;

void add(int u, int v, double w, int t)//分别对应 a,b,x,t
{//这里不细讲了 
    cnt++;
    e[cnt].to = v;
    e[cnt].dis = w;
    e[cnt].opt = t;
    e[cnt].pre = head[u];
    head[u] = cnt;
}

然后是输入部分，很简单，但要注意细节，尤其注意不能在输入时直接将流量百分比 x_i 做平方再存储，DFS时直接使用， 因为题目是这么说的：

“它们是超级管道，有超能力将流经它们的液体流量平方”

所以要用边的流量百分比 x_i 乘上 DFS 时父节点的液体量来求子节点

代码：

scanf("%d", &n);
int a, b, t;
double x;
for(int i = 1; i < n; i++)//注意只有n-1条边 
{
    scanf("%d%d%lf%d", &a, &b, &x, &t); 
    add(a, b, x / 100, t);//上面提到的双向边 
    add(b, a, x / 100, t); 
}
for(int i = 1; i <= n; i++)
{
    scanf("%lf", &k[i]);//double要用lf输入，scanf要加 &（我会告诉你我因为没加 & 卡了一个小时？） 
}

2-2 二分答案

因为是在实数域进行二分，所以代码和整数的不太一样。

我们首先定义 eps=1\times 10^{-6} 作为我们允许的误差值，一般来说我们要把这个误差设定为题目要求的平方倍，这样比较保险（其实对于这个题可以和题目要求精度相同）。

const double eps = 1e-3;

然后是改进过后的二分答案：

double l = 0;
double r = 2e9; //这里上界为题目要求L的最大值
while(l + eps < r) //eps是这么用的
{
    double mid = (l + r) / 2;
    if(check(mid)) r = mid; //如果当前答案合法，继续寻找更小的答案（更优解）
    else l = mid;//注意：这里不用-1或+1
}

2-3 DFS+check（重点）

对于 DFS，我们就按一般的图的深度优先遍历写就行。不过我们可以很容易地发现只要有一个叶子节点接收到的液体不够（即<k）那么我们二分得来的答案就不合法，这样就可以写出一个剪枝。我们定义布尔变量 f 来记录当前答案是否合法，先在 check() 函数内将 f 初始化为 1 ,然后开始DFS,过程中只要发现一个叶子节点接收到的液体不够，就将 f 赋值为 0 然后不由分说往外跳就可以了。用一个 vis 数组记录当前节点是否被搜过，这里不需要把数组在回溯时重新赋值为 0，因为这并不影响我们遍历整个图，但也可以写。

下面给出 DFS 和 check 的代码：

bool f;
bool vis[maxn];
void dfs(int u, double w) //点的编号，当前节点的液体量 
{
    if(!f) return; //这里就是剪枝了 
    if(k[u] != -1) //判断是否为叶子节点 
    {
        if(w < k[u]) f = 0; //赋值 
        return;//搜到叶子直接返回 
    }
    for(int i = head[u]; i; i = e[i].pre) //遍历每条边 
    {
        int to = e[i].to;
        double d = e[i].dis;
        if(vis[to] == 0) //防止重复搜 
        {
            vis[to] = 1;
            if(e[i].opt) dfs(to, (w * d) * (w * d)); //特判超级管道 
            else dfs(to, w * d);
            if(!f) return; //剪枝×2
        }
    }
}

bool check(double x)
{
    f = 1;
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;//记着起点也要做标记，（我会告诉你我因为没有把1做标记卡了两个小时吗？） 
    dfs(1, x);
    if(f) return true;//直接 return f 更精简 
    return false;
}

讲解就到此为止，下面上总代码：

#include<bits/stdc++.h>

#define maxn 1010

using namespace std;

const double eps = 1e-3; 

int n;
double k[maxn];
double ans;

struct edge
{
    int to, pre, opt;
    double dis;
}e[maxn << 1];
int head[maxn], cnt;

void add(int u, int v, double w, int t)
{
    cnt++;
    e[cnt].to = v;
    e[cnt].dis = w;
    e[cnt].opt = t;
    e[cnt].pre = head[u];
    head[u] = cnt;
}

bool f;
bool vis[maxn];
void dfs(int u, double w)
{
    if(!f) return;
    if(k[u] != -1)
    {
        if(w < k[u]) f = 0;
        return; 
    }
    for(int i = head[u]; i; i = e[i].pre)
    {
        int to = e[i].to;
        double d = e[i].dis;
        if(vis[to] == 0)
        {
            vis[to] = 1;
            if(e[i].opt) dfs(to, (w * d) * (w * d));
            else dfs(to, w * d);
            if(!f) return;
        }
    }
}

bool check(double x)
{
    f = 1;
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    dfs(1, x);
    if(f) return true;
    return false;
}

int main()
{
    scanf("%d", &n);
    int a, b, t;
    double x;
    for(int i = 1; i < n; i++)
    {
        scanf("%d%d%lf%d", &a, &b, &x, &t); 
        add(a, b, x / 100, t);
        add(b, a, x / 100, t); 
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%lf", &k[i]);
    }
    double l = 0;
    double r = 2e9;
    while(l + eps < r)
    {
        double mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    printf("%.5lf", r); //要用printf
    return 0; //结束罪恶的一生~~
}

最后一点，输出要用 printf 而不是 cout，因为后者精度不够，会WA。