[CCPC2019 哈尔滨] A. Artful Paintings

Description

给 \(N\) 个格子区间涂色，有两类限制条件

区间 \([L,R]\) 内至少 \(K\) 个
区间 \([L,R]\) 外至少 \(K\) 个

求最少要涂多少个格子

Solution

显然有单调性，所以二分

当限定了总个数后，差分约束来判定可行性

直接写bellman-ford就可以

训练时候忘记建 \(d[i+1]-d[i] \ge 0\) 这条边

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = 3005;

int dist[MAXN];

struct Edge {

    int u,v,cost;

    Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){};

};

vector <Edge> E;

bool bellman_ford(int start,int n) {

    for(int i=1;i<=n;i++) {

        dist[i] = INF;

    }

    dist[start]=0;

    for(int i=1;i<n;i++) {

        bool flag=false;

        for(int j=0;j<E.size();j++) {

            int u=E[j].u;

            int v=E[j].v;

            int cost=E[j].cost;

            if(dist[v]>dist[u]+cost) {

                dist[v]=dist[u]+cost;

                flag=true;

            }

        }

        if(!flag) return true;

    }

    for(int j=0;j<E.size();j++) {

        if(dist[E[j].v] > dist[E[j].u] + E[j].cost) return false;

    }

    return true;

}

int T,n,m1,m2;

struct Item {

    int l,r,k;

} r1[3005],r2[3005];

int main() {

    ios::sync_with_stdio(false);

    cin>>T;

    while(T--) {

        cin>>n>>m1>>m2;

        for(int i=1;i<=m1;i++) cin>>r1[i].l>>r1[i].r>>r1[i].k;

        for(int i=1;i<=m2;i++) cin>>r2[i].l>>r2[i].r>>r2[i].k;

        int L=0,R=n;

        while(R>L) {

            int mid=(L+R)/2;

            //cout<<"checking "<<mid<<endl;

            E.clear();

            for(int i=1;i<=n;i++)

                E.push_back(Edge(i,i+1,1)),

                E.push_back(Edge(i+1,i,0));

            for(int i=1;i<=m1;i++) {

                E.push_back(Edge(r1[i].r+1,r1[i].l,-r1[i].k));

            }

            for(int i=1;i<=m2;i++) {

                E.push_back(Edge(r2[i].l,r2[i].r+1,mid-r2[i].k));

            }

            E.push_back(Edge(1,n+1,mid));

            E.push_back(Edge(n+1,1,-mid));

            //for(int i=0;i<E.size();i++) cout<<E[i].u<<" "<<E[i].v<<" "<<E[i].cost<<endl;

            if(bellman_ford(1,n+1)) R=mid;

            else L=mid+1;

        }

        cout<<L<<endl;

    }

}

巴特西

[CCPC2019 哈尔滨] A. Artful Paintings - 差分约束,最短路

Description

Solution

最新文章

热门文章