<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
差分约束系统
虽然放在了拓扑排序部分,但这个问题用差分约束系统来解决也很合适
输入的每一对$(a,b)$都代表着一个约束关系$a >= b + 1$,抽象成节点b向节点a连一条权值为1的边,然后求系统中每个变量的最小值,出现无限增加的死锁情况就判断无解,直接套用 糖果 的方法都可以
时间复杂度
$O(n*m)$,n,m分别为节点总数和边总数
得庆幸这个问题没有出现让spfa达到理论复杂度的测试用例,在n,m都是$10^4$数量级的情况下,spfa的运行时间理论上来看是有点危险的
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
using namespace std;
vector<vector<int>> adjList;
vector<int> values, st, cnt;
queue<int> q;
int n, m, a, b;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
adjList.resize(n + 1);
//初值为100
values.resize(n + 1, 100);
st.resize(n + 1, 1);
cnt.resize(n + 1);
while (m--) {
cin >> a >> b;
//相当于不等式a >= b + 1
adjList[b].push_back(a);
}
//跑一遍spfa,有无解的情况都用字符串返回
auto giveSalary = []()->string {
for (int i = 1; i <= n; i++) q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
st[cur] = 0;
for (int nxt : adjList[cur]) {
if (values[nxt] < values[cur] + 1) {
values[nxt] = values[cur] + 1;
cnt[nxt] = cnt[cur] + 1;
if (cnt[nxt] >= n) return "Poor Xed";
if (st[nxt] == 0) {
st[nxt] = 1;
q.push(nxt);
}
}
}
}
return to_string(accumulate(values.begin() + 1, values.end(), 0));
};
cout << giveSalary() << endl;
return 0;
}
O2+输入优化,33ms
另附拓扑排序做法,时间复杂度为$O(n+m)$,细节见注释:
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <queue>
#include <string>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
//链式前向星版,邻接表版仿照差分约束法自行实现
int fin[M], nxt[M], last[N], salary[N], inDeg[N], tot = 2;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
//初始化节点1~n,初值都为100
fill(salary + 1, salary + n + 1, 100);
auto connect = [=](int s, int e) {
fin[tot] = e;
nxt[tot] = last[s];
last[s] = tot++;
};
while (m--) {
int a, b;
cin >> a >> b;
//和差分约束系统一样的建模方式
connect(b, a);
inDeg[a]++;
}
//拓扑排序也可以解决最长路问题
auto giveSalary = [=]()->string {
queue<int> q;
//统计有多少节点参与了排序
int cnt = 0;
//只需要从入度为0的节点开始搜索就行了,不用让每个节点都入队列
for (int i = 1; i <= n; i++) {
if (inDeg[i] == 0) q.push(i);
}
while (!q.empty()) {
int cur = q.front();
q.pop();
//每当一个节点出队列,就代表其参与了排序,累加到总数上
cnt++;
for (int i = last[cur]; i != 0; i = nxt[i]) {
int nx = fin[i];
//可以依据拓扑序来更新后继节点的最大值(最长路)
salary[nx] = max(salary[nx], salary[cur] + 1);
//把当前节点从原图中抽离,后果就是它的每个后继节点入度都减少了1
inDeg[nx]--;
//此时是有可能出现新的0入度节点的,要把它加入队列待排序
if (inDeg[nx] == 0) q.push(nx);
}
}
//检查是不是每个节点都参与了排序,以字符串形式输出总和的最小值或者无解信息
return (cnt < n) ? "Poor Xed" : to_string(accumulate(salary + 1, salary + n + 1, 0));
};
cout << giveSalary() << endl;
return 0;
}