• P1938 [USACO09NOV]找工就业Job Hunt


    -------------------------

    链接:Miku

    ---------------------------

    这道题本质上还是一个spfa板子,考虑一下题目的条件,到达一个城市后,肯定会赚到d的钱,那么我们把这个钱视为在路上赚的,然后到达一个城市

    立即去下一个城市,其实是等价的,我们就把边权转换成了点权。

    ----------------------------

    再考虑一下飞机,能赚的钱减去机票钱既可以了,是个负数?题目说了可以赊账。

    ----------------------------

    一直赚钱?这是什么东西,不过考虑一下把边权取负,这样能一直赚钱,不就是有负环了吗?而且还会有负边权,正好用spfa解决。

    输出怎么办?建一个超级重点,就像是奶牛在退休后,免费去一个地方安享晚年,那么那个地方在哪并不重要,对吧?

    ---------------------------

    记得取反,读入和输出的时候都是。

    而且初始化的时候,他是可以在第一个城市赚到d元的,所以要注意初始化为-d

    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    int head[100001];
    int cnt[1000001];
    int pp;
    struct b{
        int to;
        int v;
        int ne;
    }e[100001];
    int d,p,c,f,s;
    int x,y,z;
    int su;
    int dis[100001];
    int vis[100001];
    queue <int> qu;
    void add(int f,int to,int v){
        pp++;
        e[pp].v=v;
        e[pp].ne=head[f];
        e[pp].to=to;
        head[f]=pp;    
    }
    int main(){
        scanf("%d%d%d%d%d",&d,&p,&c,&f,&s);
        memset(dis,0x7f7f7f7f,sizeof(dis));
        for(int i=1;i<=p;++i){
            scanf("%d%d",&x,&y);
            add(x,y,-d);
        }
        su=c+1;
        for(int i=1;i<=f;++i){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,-(d-z));
        }
        for(int i=1;i<=c;++i){
            add(i,su,0);
        }
        qu.push(s);
        vis[s]=1;
        dis[s]=-d;
        int cntt=0;
        do{
            int u=qu.front();
            qu.pop();
            vis[u]=0;
            for(int i=head[u];i;i=e[i].ne){
                int v=e[i].to;
                if(dis[v]>dis[u]+e[i].v){
                    dis[v]=dis[u]+e[i].v;
                    if(!vis[v]){
                        vis[v]=1;
                        cnt[v]++;
                        if(cnt[v]>c){
                            cout<<-1;
                            return 0;
                        }
                        qu.push(v);
                    }
                }
            }
        }while(!qu.empty());
        cout<<-dis[su];
        return 0;
    }
    Ac
  • 相关阅读:
    Flex基础知识
    Java -version与配置的Path环境变量不一致
    Oracle 11g不能导出空表的问题解决(转)
    深入浅出JSONP--解决ajax跨域问题(转)
    Ubuntu 16.04安装docker
    观察者模式 —— java.util.Observable + java.util.Observer 源码学习
    Hashtable的contains() 、containsKey()和containsValue() 区别
    《Java核心技术卷1》拾遗
    openTSDB (rpm)安装 + Grafana 视图
    整合 springboot 和 swagger出问题
  • 原文地址:https://www.cnblogs.com/For-Miku/p/12215718.html
一二三 - 开发者的网上家园