admin 管理员组文章数量: 887021
银河
银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。
我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 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
输入样例：
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
输出样例：
11
#pragma GCC optimize(2)#include<bits/stdc++.h>#define ll long long
using namespace std;
const int N = 1e5 + 10, M = 4e5 + 10;
int head[N], ver[M], Next[M], edge[M], tot;
int hc[N], vc[M], nc[M], ec[M], tc;
int n, m;
bool ins[N];
int scc[N];
int low[N], dfn[N], num, cnt, c[N];
int d[N], v[N];
stack<int> s;inline int qread() {char cn = getchar();int x = 0;int f = 1;while (!isdigit(cn)) {if (cn == '-')f = -1;cn = getchar();}while (isdigit(cn)) {x = (x << 1) + (x << 3) + cn - '0';cn = getchar();}return x * f;
}void add(int x, int y, int z) {ver[++tot] = y;edge[tot] = z;Next[tot] = head[x];head[x] = tot;
}void add_c(int x, int y, int z) {vc[++tc] = y;ec[tc] = z;nc[tc] = hc[x];hc[x] = tc;
}void read() {n = qread(), m = qread();for (int i = 1; i <= m; i++) {int t, x, y;t = qread(), x = qread(), y = qread();if (t == 1) {add(x, y, 0);add(y, x, 0);} else if (t == 2)add(x, y, 1);else if (t == 3)add(y, x, 0);else if (t == 4)add(y, x, 1);elseadd(x, y, 0);}for (int i = 1; i <= n; i++)add(0, i, 1);
}void tarjan(int x) {dfn[x] = low[x] = ++num;s.push(x);ins[x] = true;for (int i = head[x]; i; i = Next[i]) {if (!dfn[ver[i]]) {tarjan(ver[i]);low[x] = min(low[x], low[ver[i]]);} else if (ins[ver[i]])low[x] = min(low[x], dfn[ver[i]]);}if (dfn[x] == low[x]) {cnt++;int y;do {y = s.top();s.pop();ins[y] = false;c[y] = cnt;scc[cnt]++;} while (x != y);}
}bool build() {for (int x = 0; x <= n; x++)for (int i = head[x]; i; i = Next[i]) {int y = ver[i];if (c[x] == c[y]) {if (edge[i])return false;continue;}add_c(c[x], c[y], edge[i]);}return true;
}void spfa() {queue<int> q;q.push(c[0]);v[c[0]] = true;while (!q.empty()) {int x = q.front();q.pop();v[x] = false;for (int i = hc[x]; i; i = nc[i]) {int y = vc[i];if (d[y] < d[x] + ec[i]) {d[y] = d[x] + ec[i];if (!v[y]) {v[y] = true;q.push(y);}}}}
}void solve() {ll ans = 0;for (int i = 1; i <= cnt; i++)ans += (ll) scc[i] * d[i];cout << ans;
}int main() {read();tarjan(0);if (!build()) {cout << -1;return 0;}spfa();solve();return 0;
}
本文标签： 银河
版权声明：本文标题：银河 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687544434h114201.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论