icontofig | 发布于 2019-08-18 19:27:53 | 阅读量 259 | 差分约束系统

## 题解

1.c = d 那么就是c - a = x，也就是c - a <= x, c - a >= x,也即 c - a  <= x,a - c <= -x;

2.c ≠ d 则c - a < x,d - a > x，也即c - a  <= x-1，a - d <= -x-1;

1. c = d 那么就是 c - a > x,c - b < x,也即a - c <= -x-1,c - b <= x-1;

2. c ≠ d 那么就是c - b < x,d - a > x，也即c - b <= x - 1,a - d <= -x-1;

IMPOSSIBLE的情况就是出现负环或者正环（看自己怎么定义边了，要注意SPFA中的更新的不等号方向要和建边一致，不然会WA）。

## 代码

```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 2005;
typedef long long ll;
struct edge{
int to,next;
ll dis;
}e[maxn<<5];
int cnt = 0;
int t;
int h[maxn];
int a,b,c,d;
int n,m;
ll x;
e[cnt].to = v;e[cnt].next = h[u];e[cnt].dis = d;
h[u] = cnt++;
return;
}
ll ds[maxn];
int vis[maxn],tot[maxn];
int l,r;
int SPFA(int s,int t){
for(int i = 1;i <= n;++i){
vis[i] = 0;
ds[i] = 0;
tot[i] = 0;
}
queue<int>q;
ds[s] = 0;
q.push(s);
tot[s] = 1;
while(!q.empty()){
int now = q.front();
q.pop();
vis[now] = 0;
for(int i = h[now];i != -1;i = e[i].next){
if(ds[now] + e[i].dis > ds[e[i].to]){
ds[e[i].to] = ds[now] + e[i].dis;
if(!vis[e[i].to]){
vis[e[i].to] = 1;
tot[e[i].to]++;
if(tot[e[i].to] >= n)return 0;
q.push(e[i].to);
}
}
}
}
return 1;
}
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
int main(){
t = get_num();
for(int cas = 1;cas <= t;++cas){
n = get_num();
m = get_num();
x = get_num();
for(int i = 1;i <= n;++i){
h[i] = -1;
}
cnt = 0;
for(int i = 1;i <= m;++i){
a = get_num();
b = get_num();
c = get_num();
d = get_num();
if(a == b){
if(c == d){
}
else{
}
}
else{
if(c == d){
}
else{
}
}
}
for(int i = 2;i <= n;++i){
}
int flag = SPFA(1,n);
printf("Case #%d:",cas);
if(!flag)
printf(" IMPOSSIBLE\n");
else{
for(int i = 2;i <= n;++i){
printf(" %lld",ds[i] - ds[i-1]);
}
printf("\n");
}
}
return 0;
}```

259 人读过

0 条评论