文档章节

【洛谷 P2656】采蘑菇

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 1052
阅读 9
收藏 0

好一次月赛,好一次良(bian)心(tai)的题目
我与靳小才那些不得不说的故事

因为有链接(懒得写),所以我就不上题面了~

这个题目,又是一道精彩的scc模(suan)板(fa)题

嗯,他们想尽可能多拿蘑菇,嗯
那一条边我能走几次走几次,有向图,想走几次走几次……?这是什么,告诉我——SCC!!!!
是的,就是SCC!
显然(其实没那么显然),scc上的边我可以尽可能的多拿走
just like

int get_val(int i)
{
    int ret = l[i].v;
    int nowval = l[i].v;
    while(1)
    {
        nowval = nowval * l[i].c;
        if(!nowval) return ret;
        ret += nowval;
    }
}

其中,l是边,v是权值,c是那个double

好的,就是这样,我们把scc上的搞完了
那么其他的呢……?
且慢……
不不不不不不是DAG好烦啊,咱把它搞成个DAG吧
嗯,好主意
来吧

    init();
    for(int i = 1;i <= m;i ++)
        if(scc_num[ff[i]] != scc_num[tt[i]])
            build(scc_num[ff[i]],scc_num[tt[i]],vv[i],cc[i]);

恩恩
ff是记录的
恩恩
所谓……遍历边……?
恩恩
就是这样
但是,缩点之前,我们不妨先求个scc中的ans

要不,叫点权好了
嗯,是个好主意
那么怎么办呢
val,dfs吧
dfs??
枚举

枚举
对对对
枚举多棒
就是dfs()?
好像是一样呀
本来就应该一样
不过庄周梦蝶罢了

也就是这样了:

    for(int u = 1;u <= n;u ++)
        for(int i = first[u];~i;i = next[i])
            if(scc_num[u] == scc_num[l[i].t])
                val[scc_num[u]] += get_val(i);

然后,接下来是普通的言和 tarjan

int dfs_clock,dfn[MAXN];
int scc_cnt,scc_num[MAXN];
int low[MAXN];
stack <int> s;
void dfs(int u)
{
    low[u] = dfn[u] = ++dfs_clock;
    s.push(u);
    for(int i = first[u];i != -1;i = next[i])
    {
        int v = l[i].t;
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!scc_num[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        scc_cnt ++;
        while(true)
        {
            int x = s.top();
            s.pop();
            scc_num[x] = scc_cnt;
            if(x == u)
                break;
        }
    }
    return;
}

最后,跑个spfa什么的就好了
是最长路,最长路哦~~

int use[MAXN],dis[MAXN];
deque <int> q;
void spfa(int S)
{
    memset(use,0,sizeof(use));
    memset(dis,0x80,sizeof(dis));
    dis[S] = val[S];
    use[S] = true;
    q.push_back(S);
    q.push_back(80001);
    while(!q.empty())
    {
        int u = q.front();
        q.pop_front();
        use[u] = false;
        for(int i = first[u];i != -1;i = next[i])
        {
            int v = l[i].t;
            if(dis[v] < dis[u] + l[i].v + val[v])
            {
                dis[v] = dis[u] + l[i].v + val[v];
                if(use[v])
                    continue;
                if(dis[v] > dis[q.front()])
                    q.push_front(v);
                else
                    q.push_back(v);
                use[v] = true;
            }
        }
    }
    return;
}

顺带一提,ans要这样处理

    int ans = 0;
    for(int i = 1;i <= n;i ++)
        ans = max(ans,dis[i]);

总而言之,嘛
就是这样了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
const int MAXN = 80000 + 5;
const int MAXM = 200000 + 5;
struct edge
{
    int f,t,v;
    double c;
}l[MAXM << 1];
int first[MAXN],next[MAXN << 1],tot;
void init()
{
    memset(first,0xfff,sizeof(first));
    tot = 0;
    return;
}
void build(int f,int t,int v,double c)
{
    l[++tot] = (edge){f,t,v,c};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
int dfs_clock,dfn[MAXN];
int scc_cnt,scc_num[MAXN];
int low[MAXN];
stack <int> s;
void dfs(int u)
{
    low[u] = dfn[u] = ++dfs_clock;
    s.push(u);
    for(int i = first[u];i != -1;i = next[i])
    {
        int v = l[i].t;
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!scc_num[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        scc_cnt ++;
        while(true)
        {
            int x = s.top();
            s.pop();
            scc_num[x] = scc_cnt;
            if(x == u)
                break;
        }
    }
    return;
}
int val[MAXN];
int get_val(int i)
{
    int ret = l[i].v;
    int nowval = l[i].v;
    while(1)
    {
        nowval = nowval * l[i].c;
        if(!nowval) return ret;
        ret += nowval;
    }
}
int use[MAXN],dis[MAXN];
deque <int> q;
void spfa(int S)
{
    memset(use,0,sizeof(use));
    memset(dis,0x80,sizeof(dis));
    dis[S] = val[S];
    use[S] = true;
    q.push_back(S);
    q.push_back(80001);
    while(!q.empty())
    {
        int u = q.front();
        q.pop_front();
        use[u] = false;
        for(int i = first[u];i != -1;i = next[i])
        {
            int v = l[i].t;
            if(dis[v] < dis[u] + l[i].v + val[v])
            {
                dis[v] = dis[u] + l[i].v + val[v];
                if(use[v])
                    continue;
                if(dis[v] > dis[q.front()])
                    q.push_front(v);
                else
                    q.push_back(v);
                use[v] = true;
            }
        }
    }
    return;
}
int n,m,S;
int ff[MAXM],tt[MAXM],vv[MAXM];
double cc[MAXM];
void solve()
{
    scanf("%d",&S);
    dfs(S);
        for(int u = 1;u <= n;u ++)
            for(int i = first[u];~i;i = next[i])
                if(scc_num[u] == scc_num[l[i].t])
                    val[scc_num[u]] += get_val(i);
    init();
    for(int i = 1;i <= m;i ++)
        if(scc_num[ff[i]] != scc_num[tt[i]])
            build(scc_num[ff[i]],scc_num[tt[i]],vv[i],cc[i]);
    spfa(scc_num[S]);
    int ans = 0;
    for(int i = 1;i <= n;i ++)
        ans = max(ans,dis[i]);
    printf("%d\n",ans);
    return;
}
int main()
{
    init();
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d %lf",&ff[i],&tt[i],&vv[i],&cc[i]);
        build(ff[i],tt[i],vv[i],cc[i]);
    }
    solve();
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
继初音未来之后,中国只有洛天依能匹敌?其他虚拟偶像败在……

虚拟偶像很火,但却不赚钱! 别光顾着说初音未来,或者说开始盈利的洛天依。 看看更多的虚拟偶像们吧,她们其实还在为脱贫而烦恼! 为什么会这样?答案或许让人惊讶: 虚拟偶像如初音未来、洛...

张书乐
2018/05/14
0
0
【蘑菇篇】一本跳进挨踢生活圈的日记

噔噔噔噔噔 我来啦~ 如果你玩过植物大战僵尸,那你一定知道防御僵尸那些个勇敢的蘑菇们,嘿嘿~ 没错偶就素那勇敢滴小蘑菇,可不是采姑娘的小蘑菇噢~ 话说没来51之前我也是Down友一枚,来到5...

crazys_蘑菇
2013/01/05
0
0
BZOJ 1105 [POI2007]石头花园SKA

题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1105 思路 贪心,如果所有点都在x=y这条直线的一边,那么篱笆长度一定最小,把长宽互换后篱笆长度不变,一共是4种情况(长宽分别...

wang3312362136
2018/04/24
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
“中国声谷”语音及人工智能项目集中签约仪式隆重举行

(原标题:“中国声谷”语音及人工智能项目集中签约仪式隆重举行) 11月18日,“中国声谷”语音及人工智能项目集中签约仪式在安徽合肥举行,现场展示的智能钢琴。 吴兰 摄 中新网合肥11月1...

中国新闻网
2016/11/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
29分钟前
4
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
49分钟前
5
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
50分钟前
5
0
HTML5+CSS3从入门到精通 中文pdf版​

本文转载于:专业的前端网站➵HTML5+CSS3从入门到精通 中文pdf版 HTML5+CSS3从入门到精通是通过基础知识+中小实例+综合案例的方式,讲述了用HTML5+ CSS3设计构建网站的必备知识,相对于专业指...

前端老手
52分钟前
6
0
聊聊nacos client的ConfigFilterChainManager

序 本文主要研究一下nacos client的ConfigFilterChainManager IConfigFilterChain nacos-1.1.3/api/src/main/java/com/alibaba/nacos/api/config/filter/IConfigFilterChain.java public in......

go4it
58分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部