• P1250 种树


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

    链接:Miku

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

    差分约束的可以算是例题吧,这道题我们要建立的约束系统是前缀和,毕竟要求的就是区间的和的最少的

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

    最后,用前缀和求出总区间和就行了

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

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int head[3000010];
    int p;
    int bb,ee,t;
    int sum[3000001];
    int n,h;
    struct b{
        int to;
        int ne;
        int v;
    }e[105001];
    queue <int> q;
    int vis[3000001];
    int dis[3000001];
    void add(int f,int to,int v){
        p++;
        e[p].to=to;
        e[p].ne=head[f];
        e[p].v=v;
        head[f]=p;    
    }
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&h);
        for(int i=1;i<=h;++i){
            scanf("%d%d%d",&bb,&ee,&t);
            add(ee,bb-1,-t);
        }
        for(int i=1;i<=n;++i){
            add(i-1,i,1);
            add(i,i-1,0);
        }
        int su=n+1;
        for(int i=0;i<=n;++i){
            add(su,i,0);
        }
        //memset(dis,0x7f7f,sizeof(dis));
        q.push(su);
        vis[su]=1;
        int ans=0x7f7f7f7f;
        for(int i=0;i<=n+1;++i)
            dis[i]=1;
        dis[su]=0;
        while(!q.empty()){
            int u=q.front();
            vis[u]=0;
            q.pop();
            for(int i=head[u];i!=-1;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;
                        q.push(v);
                    }
                }
            }
        }    for(int i=0;i<=n;++i)
            ans=min(ans,dis[i]);
        cout<<dis[n]-dis[0];
        return 0;
        
    }
    Ac
  • 相关阅读:
    bzoj4810 [Ynoi2017]由乃的玉米田 bitset优化+暴力+莫队
    Ionic Js六:切换开关操作
    Ionic Js五:单选框操作
    Ionic Js四:复选框
    Ionic Js三:下拉刷新
    Ionic Js二:背景层
    Ionic Js一:上拉菜单(ActionSheet)
    Ionic入门十:icon(图标)
    Ionic入门九:颜色
    Ionic入门八:头部与底部
  • 原文地址:https://www.cnblogs.com/For-Miku/p/12215977.html
一二三 - 开发者的网上家园