差分约束 + spfa + 最长路 [NOI1999] 01串


https://blog.csdn.net/Bill_Yang_2016/article/details/53556021

题目描述
  给定7个整数N,A0,B0,L0,A1,B1,L1,要求设计一个01串S=s1s2…si…sN,满足:
  1.si=0或si=1,1<=i<=N;
  2.对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1),0的个数大于等于A0且小于等于B0;
  3.对于S的任何连续的长度为L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1),1的个数大于等于A1且小于等于B1;
  例如,N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2,则存在一个满足上述所有条件的01串S=010101。

用 S 表示01序列的1的个数的前缀和,然后就可以利用题目所给的不等式以及前缀和本身存在的信息,写出不等式进行差分约束算法。

注意!用前缀和表示区间和的时候所使用的前缀和数组的 L 要减1 。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+110;
int n,a0,b0,l0,a1,b1,l1;
int s[maxn];
int cnt;

struct node{
    int from,to,val,next;
}edge[maxn];
int head[maxn];

void add(int u,int v,int val){
    edge[cnt].from = u;
    edge[cnt].to = v;
    edge[cnt].val = val;
    edge[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
}

int dis[maxn],vis[maxn],num[maxn];
const int inf = 0x3f3f3f3f;

bool spfa(){
    for(int i=0; i<=n; i++){
        dis[i] = 0;
        vis[i] = 0;
        dis[i] = inf;
        num[i] = 0;
    }
    dis[0] = 0;
    vis[0] = 1;
    num[0]++;
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=head[u]; i; i=edge[i].next){
            int v = edge[i].to;
            int w = edge[i].val;
            if(dis[v] - dis[u] > w){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                    num[v]++;
                    if(num[v] >= n) return false;
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return true;
}

int main(){
    int T=5;
    while(T--){
    cin>>n>>a0>>b0>>l0>>a1>>b1>>l1;
    dis[0] = 0;
    cnt = 1;
    memset(edge,0,sizeof(edge));
    memset(head,0,sizeof(head));
    for(int i=1; i<=n; i++){
        if(i+l0-1<=n){
            add(i-1,i+l0-1,-(l0-b0));      //注意!这个类似前缀和
            add(i+l0-1,i-1,-(-(l0-a0)));      //而前缀和计算区间内容时头要减1!!
        }
        if(i+l1-1<=n){
            add(i-1,i+l1-1,-a1);
            add(i+l1-1,i-1,-(-b1));
        }
            add(i-1,i,0);
            add(i,i-1,-(-1));
    }
    bool flag=spfa();
    if(flag==0) cout<<"-1"<<endl;
    else{
        for(int i=1; i<=n; i++){
            // cout<<dis[i]<<" ";
            if(dis[i]<dis[i-1])
                cout<<'1';
            else
                cout<<'0';
        }
        cout<<endl;
    }
    }
}

优质内容筛选与推荐>>
1、Nginx的负载均衡 - 保持会话 (ip_hash)
2、CSAPP阅读笔记-栈帧-来自第三章3.7的笔记-P164-P176
3、Nodejs总结(一)
4、C#Xpath解析HtmlDocument的使用方法与递归取得页面所有标签xpath值(附源码)
5、CodeIgniter学习笔记(十五)——CI中的Session


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号