|
|
## [$AcWing$ $368$. 银河](https://www.acwing.com/problem/content/370/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
银河中的恒星浩如烟海，但是我们只关注那些 **最亮的恒星**。
|
|
|
|
|
|
我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 $1$。
|
|
|
|
|
|
现在对于 $N$ 颗我们关注的恒星，有 $M$ 对亮度之间的相对关系已经判明。
|
|
|
|
|
|
你的任务就是求出这 $N$ 颗恒星的 **亮度值总和至少有多大**。
|
|
|
|
|
|
**输入格式**
|
|
|
第一行给出两个整数 $N$ 和 $M$。
|
|
|
|
|
|
之后 $M$ 行，每行三个整数 $T,A,B$，表示一对恒星 $(A,B)$ 之间的亮度关系。恒星的编号从 $1$ 开始。
|
|
|
|
|
|
如果 $T=1$，说明 $A$ 和 $B$ 亮度相等。
|
|
|
如果 $T=2$，说明 $A$ 的亮度小于 $B$ 的亮度。
|
|
|
如果 $T=3$，说明 $A$ 的亮度不小于 $B$ 的亮度。
|
|
|
如果 $T=4$，说明 $A$ 的亮度大于 $B$ 的亮度。
|
|
|
如果 $T=5$，说明 $A$ 的亮度不大于 $B$ 的亮度。
|
|
|
|
|
|
**输出格式**
|
|
|
输出一个整数表示结果。
|
|
|
|
|
|
若无解，则输出 $−1$。
|
|
|
|
|
|
**数据范围**
|
|
|
$N≤100000,M≤100000$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
5 7
|
|
|
1 1 2
|
|
|
2 3 2
|
|
|
4 4 1
|
|
|
3 4 5
|
|
|
5 4 5
|
|
|
2 3 5
|
|
|
4 5 1
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
11
|
|
|
```
|
|
|
|
|
|
### 二、差分约束解法
|
|
|
$N$ 颗恒星的亮度值总和 **至少** 有多大
|
|
|
|
|
|
**<font color='red'>求最小->求所有下界的最大->最长路 √</font>**
|
|
|
|
|
|
**求最大->求所有上界的最小->最短路 ×**
|
|
|
|
|
|
**最长路**
|
|
|
$dist[j] ≥ dist[t] + w[i]$
|
|
|
|
|
|
$T=1: A=B => A≥B$ $B≥A$
|
|
|
$T=2: A<B => B≥A+1$
|
|
|
$T=3: A≥B => A≥B$
|
|
|
$T=4: A>B => A≥B+1$
|
|
|
$T=5: A≤B => B≥A$
|
|
|
|
|
|
$spfa$最长路 - 做完后每个点的距离就是最小值
|
|
|
|
|
|
* 边是正的 - 存在正环 => 无解
|
|
|
* 有解
|
|
|
必须有绝对值
|
|
|
超级源点(能到所有边)
|
|
|
$x[i]≥x[0]+1$
|
|
|
|
|
|
#### 差分约束代码
|
|
|
通过了 10/11个数据
|
|
|
|
|
|
本题数据范围
|
|
|
$N≤100000,M≤100000$
|
|
|
|
|
|
和 [糖果](https://www.acwing.com/problem/content/1171/) 那道题一样一样的数据范围，肯定是测试数据进行了加强，导致卡掉了$spfa$,无论你是$stack$优化，$slf$优化，还是双端队列优化，还是什么$dfs$优化，一概无效。
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef long long LL;
|
|
|
const int N = 100010, M = 300010;
|
|
|
//与AcWing 1169. 糖果 这道题一模一样，连测试用例都一样
|
|
|
|
|
|
stack<int> q; //有时候换成栈判断环很快就能
|
|
|
LL dist[N];
|
|
|
bool st[N];
|
|
|
int cnt[N];
|
|
|
int n, m; //表示点数和边数
|
|
|
//邻接表
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
bool spfa() { //求最长路，所以判断正环
|
|
|
memset(dist, -0x3f, sizeof dist); //初始化为-0x3f
|
|
|
//差分约束从超级源点出发
|
|
|
dist[0] = 0;
|
|
|
q.push(0);
|
|
|
st[0] = true;
|
|
|
|
|
|
while (q.size()) {
|
|
|
int u = q.top();
|
|
|
q.pop();
|
|
|
st[u] = false;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int j = e[i];
|
|
|
if (dist[j] < dist[u] + w[i]) { //求最长路
|
|
|
dist[j] = dist[u] + w[i];
|
|
|
cnt[j] = cnt[u] + 1;
|
|
|
//注意多加了超级源点到各各节点的边
|
|
|
if (cnt[j] >= n + 1) return false;
|
|
|
if (!st[j]) {
|
|
|
q.push(j);
|
|
|
st[j] = true;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(h, -1, sizeof h);
|
|
|
scanf("%d %d", &n, &m);
|
|
|
for (int i = 0; i < m; i++) {
|
|
|
int op, a, b; // op为选择
|
|
|
scanf("%d %d %d", &op, &a, &b);
|
|
|
if (op == 1) /** a == b => (a >= b , b >= a) */
|
|
|
add(a, b, 0), add(b, a, 0);
|
|
|
else if (op == 2) /** b >= a + 1 */
|
|
|
add(a, b, 1);
|
|
|
else if (op == 3) /** a >= b */
|
|
|
add(b, a, 0);
|
|
|
else if (op == 4) /** a >= b + 1 */
|
|
|
add(b, a, 1);
|
|
|
else /** b >= a */
|
|
|
add(a, b, 0);
|
|
|
}
|
|
|
|
|
|
/** xi >= x0 + 1 （每个小朋友都要至少一个糖果）*/
|
|
|
//将所有节点与超级源点x0相连
|
|
|
for (int i = 1; i <= n; ++i) add(0, i, 1);
|
|
|
|
|
|
if (!spfa())
|
|
|
puts("-1");
|
|
|
else {
|
|
|
LL res = 0;
|
|
|
for (int i = 1; i <= n; ++i) res += dist[i];
|
|
|
printf("%lld\n", res);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 三、强连通分量思路
|
|
|
|
|
|
**分析**
|
|
|
用差分约束可能被卡，用 $SCC$ 稳定线性，但并非所有差分约束都能通过 $SCC$ 解决。
|
|
|
|
|
|
本题条件：
|
|
|
* ① 无负权边
|
|
|
* ② 问是否存在正环
|
|
|
* ③ 问每个点到其它点的最长距离
|
|
|
|
|
|
**性质**
|
|
|
|
|
|
* ① 环一定在 $SCC$ 中，在无负权边的前提下，若 $SCC$ 中存在一条正权边，则必存在正环
|
|
|
* ② 若不存在正环，则 $SCC$ 中每条边权都为 $0$，等价于每个点都相等
|
|
|
* ③ 在 $DAG$ 上求最长距离只需按拓扑序递推
|
|
|
|
|
|
#### 强连通分量代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef long long LL;
|
|
|
const int N = 100010, M = 600010;
|
|
|
|
|
|
int n, m;
|
|
|
int h[N], hs[N], e[M], ne[M], w[M], idx;
|
|
|
void add(int h[], int a, int b, int c) {
|
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int dist[N];
|
|
|
|
|
|
// tarjan求scc
|
|
|
int dfn[N], low[N], ts, stk[N], top, in_stk[N];
|
|
|
int id[N], scc_cnt, sz[N];
|
|
|
void tarjan(int u) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
in_stk[u] = 1;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
} else if (in_stk[v])
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++scc_cnt;
|
|
|
int x;
|
|
|
do {
|
|
|
x = stk[top--];
|
|
|
in_stk[x] = 0;
|
|
|
id[x] = scc_cnt;
|
|
|
sz[scc_cnt]++;
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
memset(h, -1, sizeof h);
|
|
|
memset(hs, -1, sizeof hs);
|
|
|
|
|
|
// 0号超级源点
|
|
|
// ∵ 恒星的亮度最暗是 1
|
|
|
// ∴ 0 ~ i 有一条边权为1的边
|
|
|
for (int i = 1; i <= n; i++) add(h, 0, i, 1);
|
|
|
|
|
|
// 求最小->求所有下界的最大->最长路 √
|
|
|
while (m--) {
|
|
|
int t, a, b;
|
|
|
scanf("%d %d %d", &t, &a, &b);
|
|
|
if (t == 1) // a=b
|
|
|
add(h, b, a, 0), add(h, a, b, 0);
|
|
|
else if (t == 2) // a < b --> b>=a+1
|
|
|
add(h, a, b, 1);
|
|
|
else if (t == 3) // a>=b+0
|
|
|
add(h, b, a, 0);
|
|
|
else if (t == 4) // a>=b+1
|
|
|
add(h, b, a, 1);
|
|
|
else
|
|
|
add(h, a, b, 0); // b>=a+0
|
|
|
}
|
|
|
// 超级源点+强连通分量+缩点
|
|
|
tarjan(0);
|
|
|
|
|
|
for (int u = 0; u <= n; u++) { // 添加上超级源点，就是n+1个点
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
int a = id[u], b = id[v];
|
|
|
if (a == b) {
|
|
|
if (w[i] > 0) { // 在同一个强连通分量中，存在边权大于0的边
|
|
|
puts("-1"); // 必然有正环,最长路存在正环，原不等式组无解
|
|
|
exit(0);
|
|
|
}
|
|
|
} else
|
|
|
add(hs, a, b, w[i]); // 建新图
|
|
|
}
|
|
|
}
|
|
|
|
|
|
for (int u = scc_cnt; u; u--) // 倒序输出拓扑序
|
|
|
for (int i = hs[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
dist[v] = max(dist[v], dist[u] + w[i]);
|
|
|
}
|
|
|
// 因为不存在正环，而且题目保证都是路径>=0,所以强连通分量中必然路径长度都是0
|
|
|
// 即是一样一样的东西
|
|
|
LL res = 0;
|
|
|
for (int i = 1; i <= scc_cnt; i++) res += (LL)dist[i] * sz[i];
|
|
|
printf("%lld\n", res);
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 四、答疑解惑
|
|
|
#### $Q:$为什么本题不需要去重边呢？
|
|
|
答：去重边也是一样可以$AC$掉的,不去也可以$AC$。道理很简单，本题只是通过边不断的求最大值，多了重边求最大值也不会使得最大值变小或变大，无所谓，要是你有路径条数这样的问题，肯定就需要去重边了。
|
|
|
|
|
|
**附：去重边代码**
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef long long LL;
|
|
|
const int N = 100010, M = 600010;
|
|
|
|
|
|
int n, m;
|
|
|
int h[N], hs[N], e[M], ne[M], w[M], idx;
|
|
|
void add(int h[], int a, int b, int c) {
|
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
int dist[N];
|
|
|
|
|
|
// tarjan求scc
|
|
|
int dfn[N], low[N], ts, stk[N], top, in_stk[N];
|
|
|
int id[N], scc_cnt, sz[N];
|
|
|
void tarjan(int u) {
|
|
|
dfn[u] = low[u] = ++ts;
|
|
|
stk[++top] = u;
|
|
|
in_stk[u] = 1;
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (!dfn[v]) {
|
|
|
tarjan(v);
|
|
|
low[u] = min(low[u], low[v]);
|
|
|
} else if (in_stk[v])
|
|
|
low[u] = min(low[u], dfn[v]);
|
|
|
}
|
|
|
if (dfn[u] == low[u]) {
|
|
|
++scc_cnt;
|
|
|
int x;
|
|
|
do {
|
|
|
x = stk[top--];
|
|
|
in_stk[x] = 0;
|
|
|
id[x] = scc_cnt;
|
|
|
sz[scc_cnt]++;
|
|
|
} while (x != u);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
scanf("%d %d", &n, &m);
|
|
|
|
|
|
memset(h, -1, sizeof h);
|
|
|
memset(hs, -1, sizeof hs);
|
|
|
|
|
|
// 0号超级源点
|
|
|
// ∵ 恒星的亮度最暗是 1
|
|
|
// ∴ 0 ~ i 有一条边权为1的边
|
|
|
for (int i = 1; i <= n; i++) add(h, 0, i, 1);
|
|
|
|
|
|
// 求最小->求所有下界的最大->最长路 √
|
|
|
while (m--) {
|
|
|
int t, a, b;
|
|
|
scanf("%d %d %d", &t, &a, &b);
|
|
|
if (t == 1) // a=b
|
|
|
add(h, b, a, 0), add(h, a, b, 0);
|
|
|
else if (t == 2) // a < b --> b>=a+1
|
|
|
add(h, a, b, 1);
|
|
|
else if (t == 3) // a>=b+0
|
|
|
add(h, b, a, 0);
|
|
|
else if (t == 4) // a>=b+1
|
|
|
add(h, b, a, 1);
|
|
|
else
|
|
|
add(h, a, b, 0); // b>=a+0
|
|
|
}
|
|
|
// 超级源点+强连通分量+缩点
|
|
|
tarjan(0);
|
|
|
|
|
|
unordered_set<LL> S; // 对连着两个不同强连通分量的边进行判重
|
|
|
for (int u = 0; u <= n; u++) { // 添加上超级源点，就是n+1个点
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
int a = id[u], b = id[v];
|
|
|
|
|
|
LL hash = a * 1000000ll + b; // 新两点a,b之间的Hash值，防止出现重边
|
|
|
if (a == b) {
|
|
|
if (w[i] > 0) { // 在同一个强连通分量中，存在边权大于0的边
|
|
|
puts("-1"); // 必然有正环,最长路存在正环，原不等式组无解
|
|
|
exit(0);
|
|
|
}
|
|
|
} else if (!S.count(hash))
|
|
|
add(hs, a, b, w[i]); // 建新图
|
|
|
}
|
|
|
}
|
|
|
|
|
|
for (int u = scc_cnt; u; u--) // 倒序输出拓扑序
|
|
|
for (int i = hs[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
dist[v] = max(dist[v], dist[u] + w[i]);
|
|
|
}
|
|
|
// 因为不存在正环，而且题目保证都是路径>=0,所以强连通分量中必然路径长度都是0
|
|
|
// 即是一样一样的东西
|
|
|
LL res = 0;
|
|
|
for (int i = 1; i <= scc_cnt; i++) res += (LL)dist[i] * sz[i];
|
|
|
printf("%lld\n", res);
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
