给出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=;
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,);
CLR(dis,0x3f);
CLR(cnt,);
q.push(n+);
dis[n+]=;
vis[n+]=;
cnt[n+]=;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=;
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 ;
q.push(v);
vis[v]=;
}
}
}
}
return ;
}
int main()
{
while(RI(n),n)
{
RI(m);
CLR(head,);
pos=;
string str;
int a,b,k;
while(m--)
{
RII(a,b);cin>>str;RI(k);
if(str=="gt")
add(a+b,a-,-k-);
else add(a-,a+b,k-);
}
rep(i,,n)
add(n+,i,);//这里ab顺序反了也会错
if(spfa())
printf("lamentable kingdom\n");
else printf("successful conspiracy\n");
}
return ;
}
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 = <<;
/*
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[+];
int dist[+];
bool bellman_ford(int n, int m)
{
//因为是求存不存在负权回路，那么只要初始化为0，更新n遍之后，如果还能再更新，那么就存在
for(int i=; i<=n; ++i)
dist[i] = ;
for(int i=; i<=n; ++i)//n+1个点，所以要更新n遍
{
for(int j=; 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=; 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[];
while(scanf("%d",&n),n)
{
scanf("%d",&m);
for(i=; i<m; ++i)
{
scanf("%d%d%s%d",&a,&b,str,&c);
if(str[]=='g')
{
es[i].from = a + b + ;
es[i].to = a;
es[i].dist = -c - ;
}
else
{
es[i].from = a;
es[i].to = a + b +;
es[i].dist = c-;
}
}
bool ret = bellman_ford(n,m);
if(ret)
puts("lamentable kingdom");
else
puts("successful conspiracy");
}
return ;
}