首页 > 编程语言 > 详细

【Luogu】P3116会议时间(拓扑排序,DP)

时间:2017-09-19 22:01:20      阅读:315      评论:0      收藏:0      [点我收藏+]

  题目链接

  本题使用拓扑排序来规划DP顺序。设s[i][j]表示i步是否能走到j这个点,e[i][j]表示i步是否能走到j这个点——用第二条路径。因为要满足无后效性和正确性,只有第i个点已经全部更新完毕的时候才能用它来更新其他的点。所以用拓扑。

  代码如下

  

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch==-)    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-0;
        ch=getchar();
    }
    return num*f;
}

int f[1000000],h,t;

struct Edge{
    int next,to,d,w;
}edge[1000010];
int head[100100],num=0;
inline void add(int from,int to,int d,int w){
    edge[++num]=(Edge){head[from],to,d,w};
    head[from]=num;
}

int indl[10010];

int s[10001][1001],e[10001][1001];

int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;++i){
        int from=read(),to=read(),d=read(),w=read();
        add(from,to,d,w);
        indl[to]++;
    }
    for(int i=2;i<=n;++i)
        if(!indl[i])    f[++t]=i;
    while(h++<t){
        int from=f[h];
        for(int i=head[from];i;i=edge[i].next){
            int to=edge[i].to;
            indl[to]--;
            if(indl[to]==0)    f[++t]=to;
        }
    }
    h=0;t=1;
    f[1]=1;
    s[0][1]=e[0][1]=1;
    while(h++<t){
        int from=f[h];
        for(int i=head[from];i;i=edge[i].next){
            
            int to=edge[i].to,d=edge[i].d,w=edge[i].w;
            for(int j=0;j<m-d;++j)    s[j+d][to]|=s[j][from];
            for(int j=0;j<m-d;++j)    e[j+w][to]|=e[j][from];
            indl[to]--;
            if(!indl[to])    f[++t]=to;
        }
    }
    for(int i=0;i<=m;++i){
        if(s[i][n]&&e[i][n]){
            printf("%d",i);
            return 0;
        }
    }
    printf("IMPOSSIBLE");
    return 0;
}

 

【Luogu】P3116会议时间(拓扑排序,DP)

原文:http://www.cnblogs.com/cellular-automaton/p/7553965.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!