【NOI 1999】01列差分制約

タイトルの説明
7個の整数N,A 0,B 0,L 0,A 1,B 1,L 1を与え、01列のS=s 1 s 2...si...sNを設計することを要求し、:1を満たす.Si=0またはsi=1,1<=i<=N;　　2.Sの任意の連続する長さL 0のサブ列sjsj+1...sj+L 0-1(1<=j<=N-L 0+1)について、0の個数はA 0以上B 0以下である.　　3.Sの任意の連続する長さL 1のサブ列sjsj+1...sj+L 1-1(1<=j<=N-L 1+1)について、1の個数はA 1以上B 1以下である.例えば、N=6、A 0=1、B 0=2、L 0=3、A 1=1、B 1=1、L 1=2であれば、上記の全ての条件を満たすS=01001列が存在する.
データ範囲
(3<=N<=1000,1<= A0<=B0<=L0<=N,1<=A1<=B1<=L1<=N)
サンプル入力
6 1 2 3 1 1 2
サンプル出力
3
問題を解く構想.
差分制約a−b<=cがb−a>=−cに変換できる場合、直接差分制約を行うことができる.
コード#コード#

#include 
#define Maxn 30005
using namespace std;
inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int S,n,N,cnt=0,dis[Maxn],vis[Maxn],tot[Maxn],h[Maxn];
struct node{int to,next,v;}e[Maxn];
void AddEdge(int x,int y,int v){e[++cnt]=(node){y,h[x],v};h[x]=cnt;}
bool SPFA(){
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int>Q;
    Q.push(S);
    dis[S]=0;
    while(Q.size()){
        int x=Q.front();
        vis[x]=false;
        Q.pop();
        for(int p=h[x];p;p=e[p].next){
            int y=e[p].to;
            if(dis[y]>dis[x]+e[p].v){
                dis[y]=dis[x]+e[p].v;
                tot[y]++;
                if(tot[y]==N+1)return false;
                if(!vis[y]){
                    vis[y]=true;
                    Q.push(y);
                }
            }
        }   
    }
    for(int i=0;i<=N-1;i++)if(dis[i]>(1<<29))return false;
    return true;
}
int main(){
    int n=Getint(),a0=Getint(),b0=Getint(),l0=Getint(),a1=Getint(),b1=Getint(),l1=Getint();
    N=n+2;
    S=n+1;
    for(int i=1;i<=n;i++){
        AddEdge(i,i-1,0);
        AddEdge(i-1,i,1);
    }
    AddEdge(S,0,0);
    for(int i=l0;i<=n;i++){
        AddEdge(i,i-l0,-(l0-b0));
        AddEdge(i-l0,i,+(l0-a0));
    }
    for(int i=l1;i<=n;i++){
        AddEdge(i,i-l1,-(a1));
        AddEdge(i-l1,i,+(b1));
    }
    if(SPFA())cout<0]<<"
";
    else cout<<"-1
";
    return 0;
}

転載先:https://www.cnblogs.com/Cedric341561/p/6811003.html