[USACO 05 DEC]Cleaning Shifts

约定不等于承诺〃 2023-08-17 17:38 63阅读 0赞

#### 题面描述 ####

约翰的奶牛们从小娇生惯养，她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，他不得不雇佣她们中的一些来清扫牛棚，约翰的奶牛中有\\(N(1 \\leq N \\leq 10000)\\)头愿意通过清扫牛棚来挣一些零花钱。

由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫。需要打扫的时段从某一天的第\\(M\\)秒开始，到第\\(E\\)秒结束\\((0 \\leq M \\leq E \\leq 86399)\\)。注意这里的秒是指时间段而不是时间点，也就是说，每天需要打扫的总时间是\\(E-M+1\\)秒。

约翰已经从每头牛那里得到了她们愿意接受的工作计划：对于某一头牛，她每天都愿意在笫 \\(T\_1 \\ldots T\_2\\)秒的时间段内工作\\((M \\leq T\_1 \\leq T\_2 \\leq E)\\)，所要求的报酬是\\(S\\)美元\\((0 \\leq S \\leq 500000)\\)。与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第\\(10 \\ldots 20\\)秒，那她总共工作的时间是\\(11\\)秒，而不是\\(10\\)秒

约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资。现在请你帮约翰决定该雇佣哪些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小。

#### 输入格式 ####

第\\(1\\)行：\\(3\\)个正整数\\(N,M,E\\)。  
第\\(2\\)到\\(N+1\\)行：第\\(i+1\\)行给出了编号为\\(i\\)的奶牛的工作计划，即\\(3\\)个正整数\\(T\_1,T\_2,S\\)。

#### 输出格式 ####

输出一个整数，表示约翰需要为牛棚清理工作支付的最少费用。如果清理工作不可能完成，那么输出\\(-1\\)。

#### 样例 ####

##### 样例输入 #####

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

##### 样例输出 #####

#### 题解 ####

可以直接利用贪心的做法，不过这里笔者使用了图论的思路进行计算。  
设每一个时间都为一个点，每头奶牛从\\(i\\)工作到\\(j\\)即是从点\\(i\\)到点\\(j\\)的一条有向边。而同时因为奶牛的工作时间可以交叉，我们要以每一个点\\(p\\)为起点，向\\(p-1\\)连一条反向边。最后，我们直接找一条从起点走到终点的最短路即可

#include<iostream>
    #include<set>
    #include<algorithm>
    #include<cstdio>
    #define maxn 100000
    #define maxm 100000
    #define X first
    #define Y second
    using namespace std;
    inline char get(){
        static char buf[30000],*p1=buf,*p2=buf;
        return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read(){
        register char c=get();register int f=1,_=0;
        while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
        while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
        return _*f;
    }
    typedef pair<int,int> pall;
    struct edge{
        int u,v,w,next;
    }E[maxm<<1];
    int p[maxn],eid=0;
    struct cmp{
        bool operator ()(const pall &a,const pall &b)const{
            if(a.Y!=b.Y)return a.Y<b.Y;
            return a.X<b.X; 
        }
    };
    void init(){
        for(register int i=0;i<maxn;i++)p[i]=-1;
        eid=0; 
    }
    void insert(int u,int v,int w){
        E[eid].u=u;
        E[eid].v=v;
        E[eid].w=w;
        E[eid].next=p[u];
        p[u]=eid++;
    }
    void insert2(int u,int v,int w){
        insert(u,v,w);
        insert(v,u,w);
    }
    int n,m,e;
    int dis[maxn],vis[maxn];
    void dijkstra(int u){
        for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0;
        dis[u]=0;vis[u]=1;
        set<pall,cmp> s;
        s.insert(make_pair(u,0));
        for(register int i=0;i<=n || s.size();i++){
            u=s.begin()->X;
            s.erase(*s.begin());
            vis[u]=1;
            for(register int j=p[u];~j;j=E[j].next){
                int v=E[j].v;
                int w=E[j].w;
                //cout<<u<<" "<<v<<" "<<w<<endl;
                if(!vis[v] && dis[v]>dis[u]+w){
                    s.erase(make_pair(v,dis[v]));
                    s.insert(make_pair(v,dis[v]=dis[u]+w));
                }
            } 
        }
    }
    int u,v,w;
    int ss[maxn],tt[maxn];
    int main(){
        //freopen("1.txt","r",stdin);
        init();
        n=read(),m=read(),e=read();
        //cout<<n<<" "<<m<<" "<<" "<<e<<endl;
        for(register int i=1;i<=n;i++){
            int s=read(),t=read(),w=read();
            insert2(s,t,w);
            insert2(s,t+1,w);
            //cout<<s<<" "<<t<<" "<<w<<endl;
        }
        for(register int i=m;i<=e;i++)insert(i+1,i,0);
        dijkstra(m);
        //for(register int i=1;i<=e;i++)cout<<dis[i]<<" ";
        if(dis[e+1]!=0x3f3f3f3f)cout<<dis[e+1];
        else cout<<-1<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Chen574118090/p/11608689.html