给出n个不等式
给出四个参数第一个数i可以代表序列的第几项，然后给出n，这样前面两个数就可以描述为ai+a(i+1)+...a(i+n)，即从i到n的连续和，再给出一个符号和一个ki
当符号为gt代表‘>’,符号为lt代表‘<'
那么样例可以表示
1 2 gt 0
a1+a2+a3>0
2 2 lt 2
a2+a3+a4<2
求是否存在不等式使得ai+a(i+1)+a(i+2)+...+a(i+n)<ki或者是ai+a(i+1)+a(i+2)+...+a(i+n)>ki 成立
显然就是一个判断是否存在负环
差分约束中
如果存在负环 说明无解 不存在
如果断路 无限解
spfa
用spfa算法还需要设置一个超级源点n+1 和所有边相连 距离为0 这样整个图就连起来了 否则是破碎的图 跑不动
注意连超级源点边的顺序
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define N 1000+5 struct node { int to,nex,v; }edge[N]; int pos=0; int head[N]; void add(int a,int b,int c) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].v=c; edge[pos].to=b; } int n,m; int vis[N]; int dis[N]; int cnt[N]; bool spfa() { queue<int>q; CLR(vis,0); CLR(dis,0x3f); CLR(cnt,0); q.push(n+1); dis[n+1]=0; vis[n+1]=1; cnt[n+1]=1; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int i=head[u];i;i=edge[i].nex) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].v) { dis[v]=dis[u]+edge[i].v; if(!vis[v]) { cnt[v]++; if(cnt[v]>n)return 0; q.push(v); vis[v]=1; } } } } return 1; } int main() { while(RI(n),n) { RI(m); CLR(head,0); pos=0; string str; int a,b,k; while(m--) { RII(a,b);cin>>str;RI(k); if(str=="gt") add(a+b,a-1,-k-1); else add(a-1,a+b,k-1); } rep(i,1,n) add(n+1,i,0);//这里ab顺序反了也会错 if(spfa()) printf("lamentable kingdom "); else printf("successful conspiracy "); } return 0; }
bellman算法判环更加简单不易错
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iostream> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <math.h> using namespace std; #pragma warning(disable:4996) typedef long long LL; const int INF = 1<<30; /* s[a+b+1] - s[a] >c --> s[a] - s[a+b+1] < -c <= -c-1 s[a+b+1] - s[a] <c --> s[a+b+1] -s[a] < c <= c-1 不连通要我们求环 */ struct Edge { int from,to,dist; }es[100+10]; int dist[100+10]; bool bellman_ford(int n, int m) { //因为是求存不存在负权回路，那么只要初始化为0，更新n遍之后，如果还能再更新，那么就存在 for(int i=1; i<=n; ++i) dist[i] = 0; for(int i=1; i<=n; ++i)//n+1个点，所以要更新n遍 { for(int j=0; j<m; ++j) { Edge &e = es[j]; //因为图是不连通的，所以如果置为INF的时候，不能在这里加这个条件 if(/*dist[e.from]!=INF &&*/ dist[e.to] > dist[e.from] + e.dist) dist[e.to] = dist[e.from] + e.dist; } } for(int j=0; j<m; ++j) { Edge &e = es[j]; if(dist[e.to] > dist[e.from] + e.dist) return false; } return true; } int main() { int n,m,a,b,c,i; char str[3]; while(scanf("%d",&n),n) { scanf("%d",&m); for(i=0; i<m; ++i) { scanf("%d%d%s%d",&a,&b,str,&c); if(str[0]=='g') { es[i].from = a + b + 1; es[i].to = a; es[i].dist = -c - 1; } else { es[i].from = a; es[i].to = a + b +1; es[i].dist = c-1; } } bool ret = bellman_ford(n,m); if(ret) puts("lamentable kingdom"); else puts("successful conspiracy"); } return 0; }