A - Artful Paintings
题意:给定数组长度 n, $m1$ 个[l,r]的染色的个数要>=$k_i$, $m2$ 个区间$[l,r]$区间外的个数要<= $k_i$,求最小区间染色数。
做出前缀和:
对于条件一:$s[r]-s[l-1]>=k_i$
对于条件二:$s[l-1]+s[n]-s[r]>=k_i$
考虑第一个条件转化为差分约束,第二个条件中 $s[n]$ 即为所求答案,$s[n]$ 越大,肯定越满足条件,不妨二分$s[n]$ :有如下不等式组:
$s[r]-s[l-1]>=k_i$
$s[l-1]+s[n]-s[r]>=k_i$
$s[i]-s[i-1]>=0$
$s[i]-s[i-1]<=1$
$s[n]-s[0]>=0$
$s[n]-s[0]<=0$
转化为差分约束之后,直接判断是否有解(即负环),注意当有 $s_i<0$ 直接无解。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=1e9; const int N=4e3+500; struct edge{ int v,w,next; }e[N*10]; int ecnt,n; int head[N],cnt[N]; void add(int u,int v,int w){ e[ecnt].v=v;e[ecnt].w=w;e[ecnt].next=head[u];head[u]=ecnt++; } ll dis[N]; bool inq[N]; bool spfa(int s){ for(int i=0;i<=n;i++)dis[i]=inf,inq[i]=0,cnt[i]=0; queue<int>Q; Q.push(s);dis[s]=0;inq[s]=1,cnt[s]=1; while(!Q.empty()){ int u=Q.front();Q.pop();inq[u]=0; for(int i=head[u];~i;i=e[i].next){ int v=e[i].v,w=e[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(dis[v]<0)return false; if(!inq[v])Q.push(v),inq[v]=1,cnt[v]++; if(cnt[v]>n){ return false; } } } } return true; } struct node{ int l,r,k; }; vector<node>G1,G2; void init(){ memset(head,-1,sizeof head); ecnt=0; } bool check(int x){ init(); for(int i=0;i<G1.size();i++){ add(G1[i].r,G1[i].l-1,-G1[i].k); } for(int i=0;i<G2.size();i++){ add(G2[i].l-1,G2[i].r,x-G2[i].k); } for(int i=1;i<=n;i++){ add(i,i-1,0); add(i-1,i,1); } add(0,n,x); add(n,0,-x); if(spfa(0))return true; return false; } int main(){ int t;cin>>t; while(t--){ int m1,m2;cin>>n>>m1>>m2; G1.clear(); G2.clear(); while(m1--){ int u,v,w;scanf("%d %d %d",&u,&v,&w); G1.push_back(node{u,v,w}); } while(m2--){ int u,v,w;scanf("%d %d %d",&u,&v,&w); G2.push_back(node{u,v,w}); } int l=0,r=n,ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid)){ // cout<<"yes "<<mid<<endl; ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); } // system("pause"); return 0; }View Code