http://poj.org/problem?id=1364
题意真心看不大懂啊。。。
现在假设有一个这样的序列，S={a1，a2，a3，a4…ai…at}
其中ai=a*si,其实这句可以忽略不看
现在给出一个不等式，使得ai+a(i+1)+a(i+2)+…+a(i+n)<ki或者是ai+a(i+1)+a(i+2)+…+a(i+n)>ki
首先给出两个数分别代表S序列有多少个，有多少个不等式
不等式可以这样描述
给出四个参数第一个数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
最后问你所有不等式是否都满足条件，若满足输出lamentable kingdom，不满足输出successful conspiracy，这里要注意了，不要搞反了
解题思路：一个典型的差分约束，很容易推出约束不等式
首先设Si=a1+a2+a3+…+ai
那么根据样例可以得出
S3-S0>0—->S0-S3<=-1
S4-S1<2—->S4-S1<=1
因为差分约束的条件是小于等于，所以我们将ki-1可以得到一个等于号
那么通式可以表示为
a b gt c
S[a-1]-s[a+b]<=-ki-1
a b lt c
S[a+b]-S[a-1]<=ki-1
那么根据差分约束建图,加入这些有向边
gt: <a+b，a-1>=-ki-1
lt: <a-1，a+b>=ki-1
再根据bellman_ford 或 SPAF 判断是否有无负环即可
若出现负环了则这个序列不满足所有的不等式
继续SPFA吧。。
这里用了无需建立超级源点的SPFA算法，在SPFA开始时将所有结点都放进队列，这样表示一开始和所有点都相连了，初始化dis数组为全0,相当于超级源点的边权值
总结：1、小于和小于等于关系的转化 2、超级源点的另一种建法
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = ; int n,m;
int cnt;
int p[maxn];
struct node
{
int u,v,w;
int next;
}edge[maxn]; void add(int u, int v, int w)
{
cnt++;
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = p[u];
p[u] = cnt;
}
//无需建立超级源点的SPFA
int SPFA()
{
queue<int> que;
while(!que.empty())
que.pop();
int dis[maxn],vexcnt[maxn];
bool inque[maxn];
memset(dis,,sizeof(dis));//dis全部初始化为0,
memset(inque,true,sizeof(inque));//inque全部初始化为1
memset(vexcnt,,sizeof(vexcnt)); for(int i = ; i <= n; i++)
que.push(i);//先让所有节点进队列
while(!que.empty())
{
int u = que.front();
que.pop();
inque[u] = false; for(int i = p[u]; i; i = edge[i].next)
{
if(dis[edge[i].v] > dis[u] + edge[i].w)
{
dis[edge[i].v] = dis[u] + edge[i].w;
if(!inque[edge[i].v])
{
inque[edge[i].v] = true;
que.push(edge[i].v);
vexcnt[edge[i].v]++;
if(vexcnt[edge[i].v] > n)//进队超过n次说明有负环
return ;
}
}
}
}
return ;
} int main()
{
while(~scanf("%d",&n) && n)
{
scanf("%d",&m);
int a,b,w;
char str[];
cnt = ;
memset(p,,sizeof(p));
for(int i = ; i < m; i++)
{
scanf("%d %d %s %d",&a,&b,str,&w);
if(strcmp(str,"gt") == )
add(a+b,a-,-w-);//加边
else add(a-,a+b,w-);//加边，均将不等式转化为 <=,
}
if(SPFA()) printf("lamentable kingdom\n");
else printf("successful conspiracy\n"); }
return ;
}
其实Bellman_ford 比SPFA更快点，普通的Bellman_ford，记得要松弛 n次。
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = ; int n,m;
int cnt;
struct node
{
int u,v,w;
}edge[maxn]; void add(int u, int v, int w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
cnt++;
}
int bellman_ford()
{
int dis[maxn];
memset(dis,,sizeof(dis)); for(int i = ; i <= n; i++)
{
for(int j = ; j < m; j++)
{
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].w)
dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
}
}
for(int j = ; j < m; j++)
{
if(dis[edge[j].v] > dis[edge[j].u] + edge[j].w)
return ;
}
return ;
}
int main()
{
while(~scanf("%d",&n) && n)
{
scanf("%d",&m);
int a,b,w;
char str[];
cnt = ;
for(int i = ; i < m; i++)
{
scanf("%d %d %s %d",&a,&b,str,&w);
if(strcmp(str,"gt") == )
add(a+b,a-,-w-);//加边
else add(a-,a+b,w-);//加边，均将不等式转化为 <=,
}
if(bellman_ford())
printf("lamentable kingdom\n");
else printf("successful conspiracy\n");
}
return ;
}
