判断是否有解可以使用差分约束。
求解赛车手的成绩的取值可以使用 Floyd。但是 \(O(n^3)\) 会 TLE。
可以先进行一次缩点。
然后进行 Floyd 求出每一个连通块内的最长路径 \(long_i\),然后最终答案是 \(\sum_{\\i=1}^{cnt} long_i\)。
存在负环就是无解。这道题无法使用 SPFA。
#include <bits/stdc++.h>
using namespace std;
/* ovo */
const int o = 0, _ = 0;
/* ovo */
const int N = 3333;
int mp[N][N];
vector <int> z[N], scc[N];
int longer[N];
int dfn[N], low[N], belong[N], counting, total, n, m1, m2;
stack <int> stk;
bool instk[N];
void doing()
{
int p = stk.top();
stk.pop();
instk[p] = false;
scc[total].push_back(p);
belong[p] = total;
}
void dfs(int now)
{
dfn[now] = low[now] = ++ counting;
stk.push(now);
instk[now] = true;
for (auto &p : z[now])
if (!dfn[p])
{
dfs(p);
low[now] = min(low[p], low[now]);
}
else if (instk[p])
low[now] = min(low[now], dfn[p]);
if (dfn[now] == low[now])
{
total ++;
while (stk.top() != now)
doing();
doing();
}
}
void tarjan()
{
for (int i = 1; i <= n; i ++)
if (!dfn[i])
dfs(i);
}
signed main()
{
cin >> n >> m1 >> m2;
memset (mp, 0x3f, sizeof mp);
for (int i = 1; i <= n; i ++)
mp[i][i] = 0;
while (m1 --)
{
int a, b;
cin >> a >> b;
z[a].push_back(b);
z[b].push_back(a);
mp[a][b] = min(mp[a][b], -1);
mp[b][a] = min(mp[b][a], 1);
}
while (m2 --)
{
int a, b;
cin >> a >> b;
z[a].push_back(b);
mp[a][b] = min(mp[a][b], 0);
}
tarjan();
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
if (belong[i] == belong[k])
for (int j = 1; j <= n; j ++)
if (belong[i] == belong[j])
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
for (int i = 1; i <= n; i ++)
if (mp[i][i])
{
cout << "NIE\n";
return 0;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (belong[i] == belong[j])
longer[belong[i]] = max(longer[belong[i]], mp[i][j]);
long long result = 0;
for (int i = 1; i <= total; i ++)
result += longer[i] + 1;
cout << result << '\n';
return o^_^o;
}
标签:P3530,tarjan,洛谷,min,int,dfn,mp,now,low
From: https://www.cnblogs.com/lxylluvio/p/luogu3530bzoj2788.html