题目分析
很恶心的很好的一道差分约束题.
由于图中有环, 考虑断环为链.
设 (Dis_{i->j}) 表示从 (i) 站点到 (j) 站点的环线长度.
设 (D_i) 表示从 (1) 站点到 (i) 站点的环线长度.
设 (Len) 表示地铁环线总长.
于是可以整理出下面的式子: (均假定 (i < j))
- (Dis_{i->j} + Dis_{j->i} = Len)
- (Dis_{i->j} = D_j - D_i)
- (Dis_{i->j} geq k => D_j - D_i geq k => D_i leq D_j - k)
- (Dis_{i->j} leq k => D_j - D_i leq k => D_j leq D_i + k)
- (Dis_{j->i} geq k => Len - Dis_{i->j} geq k => D_j <= D_i - k + Len)
- (Dis_{j->i} leq k => Len - Dis_{i->j} leq k => D_i <= D_j + k - Len)
你会发现差分约束系统中有一个未知量 (Len). 回想差分约束, 怎么判有解来着? 找负环.
题目又要输出方案数, 那该怎么做呢?
考虑图上每一个环, 其权值一定可以表示为 (val = x + k imes Len) 的形式. 那么现在分类讨论一下每一个环.
- (k = 0) 且 (x < 0) 时, (val < 0), 一定无解.
- (k < 0) 且 (x < 0) 时, (val < 0), 那么也是一定无解的.
- (k < 0) 且 (x > 0) 时, 可以通过减小 (Len) 来保证 (val > 0).
- (k > 0) 时, 可以通过增大 (Len) 来使得 (val > 0).
也就是说, 如果我们暴力枚举 (Len) 的大小然后找负环时, 我们可以通过找到的负环的 (k) 来确定 (Len) 是需要增大还是减小, 抑或是无解.
实际上, 这样思考会发现 (Len) 的合法大小一定是一段连续区间. 于是, 我们可以两次二分 (Len) 的大小, 通过找到的负环的 (k) 来缩小答案区间, 并且分别找到 (Len) 区间的左右端点.
那...怎么判无穷个解呢? 这个简单, 当答案区间大于一定阀值就可以看作是无穷解的.
代码
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
const int N = 50;
const int M = 1e4;
const long long INF = 2000000000ll * 50; //Const
int n, m1, m2, Test; //Main
int Head[N + 5], Cnt;
struct Edge {int Nxt, From, To, Val, k;} E[N + M + 5]; //Edge
int Cnte[N + 5], Pre[M + 5], St;
long long Dis[N + 5];
bool Vis[N + 5], Vs[N + 5]; //SPFA
void Fizz();
void Clear();
int SPFA(long long);
void Add(int, int, int, int);
int main() {
scanf("%d", &Test);
while(Test--) {
scanf("%d%d%d", &n, &m1, &m2), Fizz(), St = n + 1;
Add(1, n, (n > 1? -1 : 0), 1);
for(int i = 1; i < n; i ++) Add(i + 1, i, -1, 0);
for(int i = 1; i <= n; i ++) Add(St, i, 0, 0);
for(int i = 1; i <= m1; i ++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w), ++u, ++v;
if(u < v) Add(v, u, -w, 0); else Add(v, u, -w, 1);
} for(int i = 1; i <= m2; i ++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w), ++u, ++v;
if(u < v) Add(u, v, w, 0); else Add(u, v, w, -1);
} bool Flag = true;
long long Lans = INF, Rans = 0, L, R;
L = 0, R = INF;
while(L <= R) {
long long Mid = (L + R) / 2;
long long tap = SPFA(Mid);
if(tap == 2) Lans = Mid, R = Mid - 1;
else if(tap == -1) {
Flag = false; break;
} else if(tap == 0) L = Mid + 1;
else R = Mid - 1;
} L = 1, R = 2000000000ll * 50;
while(L <= R) {
long long Mid = (L + R) / 2;
long long tap = SPFA(Mid);
if(tap == 2) Rans = Mid, L = Mid + 1;
else if(tap == -1) {
Flag = false; break;
} else if(tap == 0) L = Mid + 1;
else R = Mid - 1;
} if(!Flag) printf("0
");
else if(Rans >= 2000000000ll*50) printf("-1
");
else printf("%lld
", std::max(0ll, Rans - Lans + 1));
} return 0;
} void Add(int u, int v, int w, int k) {
E[++Cnt] = (Edge){Head[u], u, v, w, k}, Head[u] = Cnt;
} void Fizz() {
memset(Head, 0, sizeof(Head)), Cnt = 0;
} void Clear() {
memset(Dis, 0x3f, sizeof(Dis));
memset(Vis, false, sizeof(Vis));
memset(Pre, 0, sizeof(Pre));
memset(Cnte, 0, sizeof(Cnte));
} int SPFA(long long K) {
Clear();
std::queue<int> Q;
Q.push(St), Dis[St] = 0, Vis[St] = true;
while(Q.size()) {
int tap = Q.front(); Q.pop(), Vis[tap] = false;
for(int i = Head[tap]; i; i = E[i].Nxt) {
int v = E[i].To;
long long DIS = Dis[tap] + E[i].Val + E[i].k * K;
if(Dis[v] > DIS) {
Pre[v] = i, Cnte[v] = Cnte[tap] + 1, Dis[v] = DIS;
if(Cnte[v] > n + 1) {
memset(Vs, false, sizeof(Vs));
int Sum = 0, tmp = tap;
for(int j = tap; j; j = E[Pre[j]].From)
if(Vs[j]) {
tmp = j; break;
} else Vs[j] = true;
Sum = E[Pre[tmp]].k;
for(int j = E[Pre[tmp]].From; j != tmp; j = E[Pre[j]].From) Sum += E[Pre[j]].k;
if(Sum == 0) return -1;
if(Sum > 0) return 0;
if(Sum < 0) return 1;
} if(!Vis[v]) Vis[v] = true, Q.push(v);
}
}
} return 2;
}