首页 > 代码库 > EOJ 3263 丽娃河的狼人传说
EOJ 3263 丽娃河的狼人传说
差分约束系统，$spfa$。
首先判断无解，若某个约束的$t$大于区间长度，则一定无解。
否则一定有解，可以得到一系列的不等式：
最终区间和大于等于目前的区间和：$S[R]-S[L-1]≥val$，
每一个位置的值小于等于$1$：$S[R]-S[R-1]≤1$，
每一个约束条件：$S[R]-S[L-1]≥t$，
最终是要求$S[n]-S[0]$最小是多少，扔进差分约束系统，跑$S[0]$到$S[n]$的最长路即可。
#include <cstdio>#include <cmath>#include <set>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;int T;int n,m,k;int dis[2000],f[2000];int h[2200000];int to[2200000];int val[2200000];int nx[2200000];int sz;int a[2000];int cas=1;void add(int a,int b,int c){ to[sz] = b; val[sz] = c; nx[sz] = h[a]; h[a] = sz++;}void spfa(){ for(int i=0;i<=n;i++) dis[i] = -n-1, f[i] = 0; queue<int>Q; Q.push(0); f[0] = 1; dis[0] =0; while(!Q.empty()) { int x =Q.front(); Q.pop(); f[x]=0; for(int i=h[x];i!=-1;i = nx[i]) { int y = to[i], cost = val[i]; if(dis[x] + cost > dis[y]) { dis[y] = dis[x] + cost; if(f[y]==0) { f[y] = 1; Q.push(y); } } } }}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=n;i++) h[i]=-1, a[i] = 0; sz=0; for(int i=1;i<=k;i++) { int x; scanf("%d",&x); a[x]=1; } for(int i=1;i<=n;i++) { a[i] = a[i]+a[i-1]; add(i,i-1,-1); } bool fail=0; for(int i=1;i<=m;i++) { int L,R,t; scanf("%d%d%d",&L,&R,&t); add(L-1,R,t); if(R-L+1<t) fail=1; } if(fail) { printf("Case %d: %d\n",cas,-1); cas++; } else { for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { add(i-1,j,a[j] - a[i-1]); } } spfa(); printf("Case %d: %d\n",cas,dis[n] - a[n]); cas++; } } return 0;}EOJ 3263 丽娃河的狼人传说
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。