差分约束系统
-
求解不等式组
- 有解 必有无穷多解(全部加上一个常数)
- 无解
-
转化为图上的最短路或者最长路
- 不等号方向为 <= 最短路
- 不等号方向为 >= 最长路
-
例子
B - A >= c (1) C - B >= a (2) C - A >= b (3)- 把A看做源点，A到A的距离是0(或者想象一个虚源点，它和A点重合)
- 那么求C的范围可以求C-A的范围(A是0),由不等式组可知 C-A >= max(b , a+c)，转化到图上，就相当于求C到源点A的距离，到底是走(3)这条边还是走(1)(2)这两条边，哪一种方案距离最长，所以需要跑最长路，得到的结果是C的最小值
- 反之，若不等号方向是 <= ，那么相当于C-A <= min(b , a+c)，所以跑的是最短路，得到的是C的最大值
-
几个约束条件
- 一个不等式组中的所有不等号必须同为>= 或者同为<=，跑相应的最长路或者最短路
- 所有数都是整数，所以a < b 可以转化为a <= b - 1,大于号同理；等于号转化为两个对称不等式
- 若跑最短路，图中有负环，必无解，其数学意义是小于无穷小，这是不存在的
- 若跑最长路，图中存在正环，必无解，其数学意义是大于无穷大，这是不存在的
- 综上，跑最短(最长)路的算法选择SPFA
-
变量值的限定(仅供参考，不是很严谨)
- 取决于每个点到虚源点的初始距离和求的是最小值还是最大值，不妨要求的是最小值，则跑的是最长路
- 一开始将所有点都丢进SPFA的队列中，相当于设想了虚源点，若初始距离(所有点到虚源点的距离)初始化为a，则最后的解向量中每一个变量的值都至少是a,类比例子可以知道为什么，C-A>=x,A是a，那么C必然大于等于a
- 若求的是最大值，则跑的是最短路，初始与虚源点的距离为a，则最后的解向量中每一个变量的值不超过a
#include<iostream>
#include<queue>
#include<list>
#include<vector>
#include<cstring>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define MS(x,i) memset(x,i,sizeof(x))
#define rep(i,s,e) for(int i=s; i<=e; i++)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define debug printf("debug......
");
#define pfd(x) printf("%d
",x)
#define pfl(x) printf("%lld
",x)
const double eps=1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x7fffffff;
const int maxn = 1e5+10;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0 , 0};
const int M = 1e5+10;
int n,m;//顶点数边数
int head[maxn];//记录顶点的第一条边
int cnt; //记录当前是第几条边
//边
struct node{
int to;
int w;
int nxt;
}edge[2*M]; //无向图的话要开两倍
//加边
void addEdge(int u, int v, int w){
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
bool vis[maxn];//记录是否在队列
int dis[maxn];//记录当前最短距离
int in[maxn];//记录结点被入队了多少次，如果大于n则说明有负环
//int path[maxn];//记录前驱
bool SPFA(int s){
queue<int> q;
//把所有点一开始都丢进队列，事实上相当于建立一个虚源点，并限定定所有点到其距离为1，保证了所有变量值大于等于1
rep(i, 1, n){
q.push(i);
dis[i] = 1;
vis[i] = 1;
}
while(!q.empty()){
int fr = q.front();
q.pop();
vis[fr] = 0;//出队后置为0
//对每个与fr相连的顶点 对其进行松弛操作
for(int i=head[fr]; i!=0; i=edge[i].nxt){
int v = edge[i].to;
int w = edge[i].w;
//这里跑最长路 所以取小于号
if(dis[v] < dis[fr] + w){
//pre[v] = fr;
dis[v] = dis[fr] + w;
if(!vis[v]){
q.push(v);
in[v]++;
vis[v] = 1;
if(in[v] > n) return false;
}
}
}
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
int u,v,w;
cnt = 1;//第一条边
MS(head , 0 );
//rep(i,1,n) addEdge(0,i,1);
rep(i , 1, m){
cin>>w>>u>>v;
if(w == 1){
addEdge(u , v , 0);
addEdge(v , u , 0);
}
else if(w == 2){
addEdge(u , v, 1);
}
else if(w == 3){
addEdge(v , u , 0);
}
else if(w == 4){
addEdge(v, u, 1);
}
else if(w == 5){
addEdge(u , v , 0);
}
}
ll ans = 0;
if(SPFA(0)){
rep(i,1,n)
ans += dis[i];
cout<<ans<<endl;
}
else{
cout<<-1<<endl;
}
return 0;
}
#include<iostream>
#include<queue>
#include<list>
#include<vector>
#include<cstring>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define MS(x,i) memset(x,i,sizeof(x))
#define rep(i,s,e) for(int i=s; i<=e; i++)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define debug printf("debug......
");
#define pfd(x) printf("%d
",x)
#define pfl(x) printf("%lld
",x)
const double eps=1e-8;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x7fffffff;
const int maxn = 2e2+10;
const int M = 2e2+10;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0 , 0};
int n,m;//顶点数边数
int head[maxn];//记录顶点的第一条边
int cnt; //记录当前是第几条边
//边
struct node{
int to;
int w;
int nxt;
}edge[2*M]; //无向图的话要开两倍
//加边
void addEdge(int u, int v, int w){
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt++;
}
bool vis[maxn];//记录是否在队列
int dis[maxn];//记录当前最短距离
int in[maxn];//记录结点被入队了多少次，如果大于n则说明有负环
bool SPFA(){
queue<int> q;
rep(i, 0, n){
q.push(i);
//初始化一下dis 数值无所谓 可以初始化为0
dis[i] = 10;
vis[i] = 1;
in[i] = 1;
}
while(!q.empty()){
int fr = q.front();
q.pop();
vis[fr] = 0;//出队后置为0
//对每个与fr相连的顶点 对其进行松弛操作
for(int i=head[fr]; i!=0; i=edge[i].nxt){
int v = edge[i].to;
int w = edge[i].w;
//跑最短路
if(dis[v] > dis[fr] + w){
//pre[v] = fr;
dis[v] = dis[fr] + w;
if(!vis[v]){
q.push(v);
in[v]++;
vis[v] = 1;
if(in[v] > n) return false;
}
}
}
}
return true;
}
int main(){
while(sc(n) != EOF){
cnt = 1;
MS(head , 0);
MS(vis , 0);
if(n == 0 )break;
sc(m);
int si,ni,ki;
char oi[5];
rep(i,1,m){
scanf("%d%d%s%d", &si, &ni, &oi, &ki);
if(oi[0] == 'g'){
addEdge(si+ni , si-1, -1-ki);
}
else{
addEdge(si-1 , si+ni, ki-1);
}
}
if(!SPFA()) printf("successful conspiracy
");
else printf("lamentable kingdom
");
}
return 0;
}