- 首页 > it技术 > >
/**
* @file main.cpp
* @brief 差分约束系统,题目意思为:
*国王给出m组假设,计算满足所有假设的数组是否存在
*假设分两种:
*1. 从si开始的连续ni+1个数字相加小于ki
*2. 从si开始的连续ni+1个数字相加大于ki
*
*令s[i]表示a[0]+a[1]+...+a[i],则以上条件可以描述为:
*1. s[si + ni] - s[si - 1] < ki
*2. s[si + ni] - s[si - 1] > ki
*
*即(可以把大于等于化为大于,通过整数运算)
*1. if (s[si + ni] + (1 - ki) > s[si - 1])
*s[si - 1] = s[si + ni] + (1 - ki)
*2. if (s[si - 1] + (1 + ki) > s[si + ni])
*s[si + ni] = s[si - 1] + (1 + ki)
*
*构图:
*1. (si + ni, si - 1)添加权值1-ki
*2. (si - 1, si + ni)添加权值1+ki
*
*使用bellman_ford检测是否有负环即可
*
* @author yekeren
* @version 1.0.0
* @date 2013-06-07
*/#include
#include #define LIMIT 101struct edge_t {
int a, b, c;
} k[LIMIT];
bool bellman_ford(int n, int m)
{
int dist[LIMIT] = { 0 };
for (int t = 0;
t < n - 1;
++t)
{
for (int i = 0;
i < m;
++i)
{
if (dist[k[i].a] + k[i].c > dist[k[i].b]) {
dist[k[i].b] = dist[k[i].a] + k[i].c;
}
}
}//
//已经松弛n-1次,看能否再松弛
//
bool flag = false;
for (int i = 0;
i < m;
++i)
{
if (dist[k[i].a] + k[i].c > dist[k[i].b])
{
dist[k[i].b] = dist[k[i].a] + k[i].c;
return false;
}
}return true;
}int main(int argc, char *argv[])
{
int n, m;
while (std::cin >> n, n != 0)
{
std::cin >> m;
for (int i = 0;
i < m;
++i)
{
char oi[4];
int si, ni, ki;
std::cin >> si >> ni >> oi >> ki;
if (strcmp(oi, "gt") == 0)
{
k[i].a = si - 1;
k[i].b = si + ni;
k[i].c = 1 + ki;
}
else if (strcmp(oi, "lt") == 0)
{
k[i].a = si + ni;
k[i].b = si - 1;
k[i].c = 1 - ki;
}
}if (bellman_ford(n + 1, m)) {
std::cout << "lamentable kingdom" << std::endl;
} else {
std::cout << "successful conspiracy" << std::endl;
}
}return 0;
}
推荐阅读
