洛谷 P1113 杂务（拓扑排序/巧妙做法）

62 阅读 0 评论 41 点赞

我是靠谱客的博主平淡人生，最近开发中收集的这篇文章主要介绍洛谷 P1113 杂务（拓扑排序/巧妙做法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

直观做法：拓扑排序

巧妙做法：根据某个任务的前驱标号必定比其小，可以不断地动态更新每个任务完成的最终时间。

// 拓扑排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 10010
#define MAXM 200010
using namespace std;
int n,u,v,w,cnt,in[MAXN],head[MAXN],mx[MAXN],res,t[MAXN];
queue<int> q;
struct Edge{
    int to,nxt;
}edge[MAXM];
void addedge(int u,int v){
    edge[cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt++;
}
void topo(){
    for(int i=1;i<=n;i++)if(in[i]==0)q.push(i),mx[i]=t[i];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            in[v]--;if(!in[v])q.push(v);
            mx[v]=max(mx[v],mx[u]+t[v]);
        }
    }
    for(int i=1;i<=n;i++)res=max(res,mx[i]);
}
int main(){
#ifdef WINE
    freopen("data.in","r",stdin);
#endif
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v,&w);
        t[v]=w;
        while(scanf("%d",&u)&&u){
            in[v]++;
            addedge(u,v);
        }
    }
    topo();
    printf("%d",res);
    return 0;
}

// 不用拓扑排序的巧妙做法
#include<iostream>
#include<cstdio>
#define MAXN 10010
using namespace std;
int n,len,u,v,res[MAXN],ans;
int main(){
#ifdef WINE
    freopen("data.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v,&len);
        int tmp=0;
        while(scanf("%d",&u)&&u)tmp=max(res[u],tmp);
        res[v]=tmp+len;
        ans=max(res[v],ans);
    }
    printf("%dn",ans);
    return 0;
}