2022 02 20 DAGDP&SCC&2SAT
Let Me Count The Ways¶
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
typedef long long ll;
ll arr[N];
const int coin[] = {1, 5, 10, 25, 50};
int main() {
int x;
arr[0] = 1;
for (auto x : coin) {
for (int i = 0; i <= 30000; ++i) {
arr[i + x] += arr[i];
}
}
while (cin >> x) {
ll ans = arr[x];
if (ans != 1) {
printf("There are %lld ways to produce %d cents change.\n", ans, x);
} else {
printf("There is only 1 way to produce %d cents change.\n", x);
}
}
}The Tower of Babylon¶
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n, m, id;
struct cube {
int x, y, h;
bool operator>(const cube& b) const {
return (x > b.x && y > b.y) || (x > b.y && y > b.x);
}
} c[N];
int dp[N];
int get(int id) {
int& ans = dp[id];
if (ans > 0) return ans;
ans = c[id].h;
for (int i = 1; i <= m; ++i) {
if (c[id] > c[i]) {
ans = max(ans, get(i) + c[id].h);
}
}
return ans;
}
int main() {
int tc = 0;
while (cin >> n && n) {
memset(dp, 0, sizeof(dp));
m = n * 3;
for (int i = 1; i <= m; i += 3) {
int x, y, h;
cin >> x >> y >> h;
c[i] = {x, y, h};
c[i + 1] = {h, x, y};
c[i + 2] = {y, h, x};
}
int ans = 0;
for (int i = 1; i <= m; i++) {
ans = max(get(i), ans);
}
printf("Case %d: maximum height = %d\n", ++tc, ans);
}
}A Spy in the Metro¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ti[55]; // 每辆火车行驶一站的时间
// has_train[t][i][0]：在t时刻i车站是否有向右的火车
bool has_train[2005][55][2];
// dp[i][j]：在i时刻，你在车站j最少还需要等待多长时间
int dp[2055][55];
int main() {
int tc = 0;
int n;
while (cin >> n && n) {
int t;
cin >> tac;
memset(has_train, 0, sizeof(has_train));
for (int i = 1; i <= n - 1; ++i) {
cin >> ti[i];
}
int m1;
cin >> m1;
for (int i = 0; i < m1; ++i) {
// rightward
int d;
cin >> d;
for (int j = 1; j <= n; ++j) {
if (d > t) break;
has_train[d][j][0] = true;
d += ti[j];
}
}
int m2;
cin >> m2;
for (int i = 0; i < m2; ++i) {
// leftward
int e;
cin >> e;
for (int j = n; j >= 1; --j) {
if (e > t) break;
has_train[e][j][1] = true;
e += ti[j - 1]; // leftward
}
}
for (int j = 0; j < n; ++j) dp[t][j] = 5000;
dp[t][n] = 0;
for (int i = t - 1; i >= 0; --i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = dp[i + 1][j] + 1;
// rightward
if (j < n && i + ti[j] <= t && has_train[i][j][0]) {
dp[i][j] = min(dp[i][j], dp[i + ti[j]][j + 1]);
}
// leftward
if (j > 1 && i + ti[j - 1] <= t && has_train[i][j][1]) {
dp[i][j] = min(dp[i][j], dp[i + ti[j - 1]][j - 1]);
}
}
}
printf("Case Number %d: ", ++tc);
if (dp[0][1] >= 5000)
printf("impossible\n");
else
printf("%d\n", dp[0][1]);
}
}Timeline¶
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int N = 100000 + 5;
vector<pi> adj[N];
int s[N], t[N];
int main() {
int n, m, c;
queue<int> q;
cin >> n >> m >> c;
for (int i = 1; i <= n; ++i) cin >> s[i];
for (int i = 1; i <= c; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
t[v]++;
}
// 拓扑排序
for (int i = 1; i <= n; ++i)
if (!t[i]) q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto [v, w] : adj[u]) {
s[v] = max(s[v], s[u] + w);
t[v]--;
if (!t[v]) q.push(v);
}
}
for (int i = 1; i <= n; ++i) cout << s[i] << '\n';
}Substring¶
// 拓扑排序可以排非连通图？！
#include <bits/stdc++.h>
using namespace std;
const int N = 300'000 + 10;
// dp[i][alpha] 表示在字符串前i个字符组成的图中
// alpha这个字符的最大数量
int dp[N][26];
char s[N];
int indeg[N];
vector<int> adj[N];
int m, n;
int main() {
cin >> n >> m >> s + 1;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
indeg[v]++;
adj[u].push_back(v);
}
queue<int> q;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (indeg[i] == 0) {
q.push(i);
dp[i][s[i] - 'a'] = 1;
}
}
while (q.size()) {
int u = q.front();
q.pop();
cnt++;
for (auto v : adj[u]) {
for (int j = 0; j < 26; ++j) {
dp[v][j] = max(dp[v][j], dp[u][j] + (s[v] - 'a' == j));
}
indeg[v]--;
if (indeg[v] == 0) q.push(v);
}
}
int ans = -1;
// 因为这道题特殊所以找答案需要找遍dp数组
if (cnt == n) {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
ans = max(ans, dp[i][j]);
}
}
}
cout << ans << endl;
}Fox and Names¶
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int A = 30;
int n;
vector<int> adj[A];
int indeg[A];
string name[N];
int enc(int a) {
if (a == ' ')
return 0;
else
return a - 'a' + 1;
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> name[i];
name[i] += ' ';
}
for (int i = 0; i < n - 1; ++i) {
int pos = 0;
while (name[i][pos] == name[i + 1][pos]) pos++;
int u = enc(name[i][pos]), v = enc(name[i + 1][pos]);
if (v == 0) { // xy > x
cout << "Impossible\n";
return 0;
}
adj[u].push_back(v);
indeg[v]++;
}
queue<int> q;
int cnt = 0;
for (int i = 0; i <= 26; ++i) {
if (!indeg[i]) q.push(i);
}
string ans;
while (q.size()) {
int u = q.front();
q.pop();
if (u) {
ans += char(u + 'a' - 1);
cnt++;
}
// cout << ans << endl;
for (int v : adj[u]) {
indeg[v]--;
if (!indeg[v]) q.push(v);
}
}
if (cnt == 26)
cout << ans << endl;
else
cout << "Impossible\n";
}受欢迎的牛 G¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;
vector<int> adj[N];
int dfn[N], low[N], deg[N], sz[N];
int scc[N], sccidx; // 节点i所在SCC的编号
bool instack[N];
int n, m;
int dfncnt;
stack<int> s;
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
s.push(u);
instack[u] = true;
for (auto v : adj[u]) {
if (!dfn[v]) { // v未被搜索过
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v]) // v在栈中
low[u] = min(low[u], dfn[v]);
}
int k = -1; // 不必担心，k在使用前一定是赋值了的
if (low[u] == dfn[u]) {
++sccidx;
do {
k = s.top();
s.pop();
instack[k] = false;
scc[k] = sccidx;
sz[sccidx]++;
} while (u != k);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) tarjan(i);
}
for (int u = 1; u <= n; ++u) {
for (auto v : adj[u]) {
if (scc[u] != scc[v]) {
deg[scc[u]]++; // 遍历点并记录出度
}
}
}
bool id = 0;
for (int i = 1; i <= sccidx; ++i) {
if (!deg[i]) {
if (id) {
// 两次出现出度为0的点，直接输出0
puts("0");
return 0;
}
id = i;
}
}
cout << sz[id] << endl;
}The Largest Clique¶
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
vector<int> adj[N], sccadj[N];
int dfn[N], low[N], deg[N], sz[N], scc[N], memo[N], dfncnt, scccnt, ans;
bool instk[N];
int n, m;
stack<int> s;
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
s.push(u);
instk[u] = true;
for (auto v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scccnt++;
int k = -1;
do {
k = s.top();
s.pop();
sz[scccnt]++;
instk[k] = false;
scc[k] = scccnt;
} while (k != u);
}
}
int dfs(int u) {
if (memo[u]) return memo[u];
for (const int v : sccadj[u]) memo[u] = max(memo[u], dfs(v));
return memo[u] = memo[u] + sz[u];
}
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> n >> m;
for (int *arr : {dfn, low, deg, sz, scc, memo}) {
memset(arr, 0, sizeof(dfn));
}
memset(instk, 0, sizeof instk);
while (s.size()) s.pop();
dfncnt = scccnt = ans = 0;
for (auto &v : {adj, sccadj})
for (int i = 1; i <= n; ++i) v[i].clear();
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; ++u) {
for (int v : adj[u]) {
if (scc[u] != scc[v]) {
sccadj[scc[u]].push_back(scc[v]);
}
}
}
for (int i = 1; i <= scccnt; ++i) {
ans = max(ans, dfs(i));
}
cout << ans << endl;
}
}
最大半连通子图¶
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dfn[N], low[N], deg[N], sz[N], scc[N], dfncnt, scccnt;
bool instk[N];
vector<int> adj[N], sccadj[N];
stack<int> s;
int f[N], g[N], used[N];
int n, m, x;
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
s.push(u);
instk[u] = true;
for (auto v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scccnt++;
int k = -1;
do {
k = s.top();
s.pop();
sz[scccnt]++;
instk[k] = false;
scc[k] = scccnt;
} while (k != u);
}
}
int main() {
cin >> n >> m >> x;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; ++u) {
f[u] = sz[u];
g[u] = 1;
for (auto v : adj[u]) {
if (scc[u] == scc[v]) continue;
sccadj[scc[u]].push_back(scc[v]);
}
}
for (int u = scccnt; u >= 1; --u) {
for (int v : sccadj[u]) {
if (used[v] == u) continue;
used[v] = u;
if (f[v] < f[u] + sz[v]) {
f[v] = f[u] + sz[v];
g[v] = g[u];
} else if (f[v] == f[u] + sz[v]) {
g[v] += g[u];
g[v] %= x;
}
}
}
int ans = 0, tmp = 0;
for (int i = 1l; i <= scccnt; ++i) {
if (f[i] > ans) {
ans = f[i];
tmp = g[i];
} else if (f[i] == ans) {
tmp += g[i];
tmp %= x;
}
}
cout << ans << endl << tmp << endl;
}Quantum Superposition¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 10;
typedef long long ll;
vector<int> adj1[N], adj2[N];
vector<int> dis1, dis2;
bool nm[N * 2];
bool vis[N][N];
int n1, n2, m1, m2;
void dfs(vector<int> &dis, int n, vector<int> (&adj)[N], int u, int dep) {
if (u == n) dis.push_back(dep);
for (int v : adj[u]) {
if (!vis[v][dep + 1]) {
vis[v][dep + 1] = true;
dfs(dis, n, adj, v, dep + 1);
}
}
}
int main() {
cin >> n1 >> n2 >> m1 >> m2;
for (int i = 1; i <= m1; i++) {
int x, y;
cin >> x >> y;
adj1[x].push_back(y);
}
for (int i = 1; i <= m2; i++) {
int x, y;
cin >> x >> y;
adj2[x].push_back(y);
}
dfs(dis1, n1, adj1, 1, 0);
memset(vis, 0, sizeof(vis));
dfs(dis2, n2, adj2, 1, 0);
for (int x : dis1) {
for (int y : dis2) {
nm[x + y] = true;
}
}
int k, q;
cin >> k;
while (k--) {
cin >> q;
cout << (nm[q] ? "YES\n" : "NO\n");
}
return 0;
}Milking Order G¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
vector<int> adj[N];
vector<int> vec[N];
int indeg[N];
// 考虑前x条信息时的图
void build(int x) {
for (int i = 0; i <= n; ++i) adj[i].clear();
memset(indeg, 0, sizeof indeg);
for (int i = 1; i <= x; ++i) {
for (int j = 0; j < vec[i].size() - 1; ++j) {
int u = vec[i][j], v = vec[i][j + 1];
adj[u].push_back(v);
indeg[v]++;
}
}
}
bool check(int x) {
build(x);
queue<int> q;
int cnt = 0;
for (int i = 1; i <= n; ++i)
if (!indeg[i]) q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
cnt++;
for (int v : adj[u]) {
indeg[v]--;
if (!indeg[v]) q.push(v);
}
}
return cnt == n;
}
void get_ans(int x) {
build(x);
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 1; i <= n; ++i)
if (!indeg[i]) q.push(i);
while (q.size()) {
int u = q.top();
q.pop();
cout << u << ' ';
for (int v : adj[u]) {
indeg[v]--;
if (!indeg[v]) q.push(v);
}
}
cout << endl;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int si;
cin >> si;
for (int j = 1; j <= si; ++j) {
int x;
cin >> x;
vec[i].push_back(x);
}
}
int l = 1, r = m, ans;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid))
ans = mid, l = mid + 1;
else
r = mid - 1;
}
get_ans(ans);
}Proving Equivalences¶
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int dfn[N], low[N], deg[N], sz[N], scc[N], outdeg[N], indeg[N], dfncnt, scccnt;
bool instk[N];
vector<int> adj[N];
stack<int> s;
int n, m;
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
s.push(u);
instk[u] = true;
for (auto v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scccnt++;
int k = -1;
do {
k = s.top();
s.pop();
sz[scccnt]++;
instk[k] = false;
scc[k] = scccnt;
} while (k != u);
}
}
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> n >> m;
for (int *arr : {dfn, low, deg, sz, scc, outdeg, indeg})
memset(arr, 0, sizeof dfn);
memset(instk, 0, sizeof instk);
while (s.size()) s.pop();
dfncnt = scccnt = 0;
for (int i = 1; i <= n; ++i) adj[i].clear();
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; ++u)
for (int v : adj[u])
if (scc[u] != scc[v]) ++outdeg[scc[u]], ++indeg[scc[v]];
if (scccnt == 1) {
cout << 0 << endl;
} else {
int cntin = 0, cntout = 0;
for (int i = 1; i <= scccnt; ++i) {
if (!indeg[i]) ++cntin;
if (!outdeg[i]) ++cntout;
}
cout << max(cntin, cntout) << endl;
}
}
}软件安装¶
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int dfn[N], low[N], deg[N], sz[N], scc[N], outdeg[N], indeg[N], dfncnt, scccnt;
bool instk[N];
vector<int> adj[N];
int w[N], a[N], d[N];
int W[N], V[N], dp[N][N];
stack<int> s;
int n, m;
void tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
s.push(u);
instk[u] = true;
for (auto v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scccnt++;
int k = -1;
do {
k = s.top();
s.pop();
sz[scccnt]++;
instk[k] = false;
scc[k] = scccnt;
W[scccnt] += w[k];
V[scccnt] += a[k];
} while (k != u);
}
}
void solve(int u) {
for (int i = W[u]; i <= m; ++i) {
dp[u][i] = V[u];
}
for (auto v : adj[u]) {
solve(v);
int k = m - W[u];
for (int i = k; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[u][i + W[u]] = max(dp[u][i + W[u]], dp[v][j] + dp[u][i + W[u] - j]);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> w[i];
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) {
cin >> d[i];
if (d[i]) adj[d[i]].push_back(i);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan(i);
for (int i = 0; i <= n; ++i) adj[i].clear();
for (int i = 1; i <= n; ++i) {
if (scc[d[i]] != scc[i]) {
adj[scc[d[i]]].push_back(scc[i]);
indeg[scc[i]]++;
}
}
for (int i = 1; i <= scccnt; ++i) {
if (!indeg[i]) adj[0].push_back(i);
}
solve(0);
cout << dp[0][m] << endl;
}Astronauts¶
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200100, maxm = 400100;
int n, m, head[maxn], len, age[maxn];
bool vis[maxn];
queue<int> q;
struct edge {
int to, next;
} edges[maxm];
void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
void add_sub(int u, int a, int v, int b) {
add_edge(u + n * (a ^ 1), v + n * b);
add_edge(v + n * (b ^ 1), u + n * a);
}
bool dfs(int u) {
if (vis[u + n * (u <= n ? 1 : -1)]) {
return 0;
}
if (vis[u]) {
return 1;
}
vis[u] = 1;
q.push(u);
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (!dfs(v)) {
return 0;
}
}
return 1;
}
bool twoSAT() {
for (int i = 1; i <= n; ++i) {
if (!vis[i] && !vis[i + n]) {
while (q.size()) {
q.pop();
}
if (!dfs(i)) {
while (q.size()) {
vis[q.front()] = 0;
q.pop();
}
if (!dfs(i + n)) {
return 0;
}
}
}
}
return 1;
}
int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
len = 0;
memset(vis, 0, sizeof(vis));
memset(head, 0, sizeof(head));
int sum = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &age[i]);
sum += age[i];
}
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
if (u == v) {
continue;
}
add_sub(u, 0, v, 0);
if ((age[u] * n >= sum) == (age[v] * n >= sum)) {
add_sub(u, 1, v, 1);
}
}
if (!twoSAT()) {
puts("No solution.");
continue;
}
for (int i = 1; i <= n; ++i) {
if (vis[i + n]) {
puts("C");
} else if (age[i] * n >= sum) {
puts("A");
} else {
puts("B");
}
}
}
return 0;
}Now or Later¶
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
#define ll long long
const int N = 1e4 + 10;
int dfn[N],low[N],c[N],cnt,num,n;
bool ins[N];
stack <int> s;
vector <int> G[N];
void tarjan(int x) {
dfn[x] = low[x] = ++cnt;
s.push(x);ins[x] = 1;
for (int i = 0;i < G[x].size();++i) {
int v = G[x][i];
if (!dfn[v]) {
tarjan(v);
low[x] = min(low[x],low[v]);
} else if (ins[v]) {
low[x] = min(low[x],dfn[v]);
}
}
if (dfn[x] == low[x]) {
int y;c[x] = ++num;
do {
y = s.top();s.pop();
c[y] = num;ins[y] = 0;
} while (x != y);
}
}
int a[N][2];
bool check(int cap) {
for (int i = 1;i <= 2 * n;++i) G[i].clear();
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(c,0,sizeof c);
memset(ins,0,sizeof ins);
cnt = num = 0;
for (int i = 1;i <= n;++i) {
for (int qwq = 0;qwq <= 1;++qwq) {
for (int j = i + 1;j <= n;++j) {
for (int qaq = 0;qaq <= 1;++qaq) {
if (abs(a[i][qwq] - a[j][qaq]) < cap) {
G[i + n * qwq].push_back(j + n * (qaq ^ 1));
G[j + n * qaq].push_back(i + n * (qwq ^ 1));
}
}
}
}
}//重新建图的过程
for (int i = 1;i <= 2 * n;++i) if (!dfn[i]) tarjan(i);
for (int i = 1;i <= n;++i) {
if (c[i] == c[i+n]) return 0;
}
return 1;
}
void solve() {
memset(ins,0,sizeof ins);
tot = 0;
int l = 0,r = 0,ans = 0;
for (int i = 1;i <= n;++i) scanf("%d %d\n",&a[i][0],&a[i][1]),r = max(r,a[i][1]);
while (l < r - 1) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid;
}
cout << l << endl;
return ;
}
signed main() {
while (scanf("%d\n",&n) != EOF) solve();
return 0;
}Grass Cownoisseur¶
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
struct point{
int to,next;
}edge[200000],edge1[200000][3];
int cnt,n,m,ans,t,tot;
int head[200000],head1[200000][3],d[200000][3],dfn[200000],low[200000],v[200000];
int node[200000],f[200000][3],size[200000],q[200000];
stack<int>s;
void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void add1(int u,int v,int ch)
//ch为1的时候表示原本的缩点后的图，2的时候表示所有边都已反向过的图
{
if (ch==1) cnt++;
d[v][ch]++;
edge1[cnt][ch].to=v;
edge1[cnt][ch].next=head1[u][ch];
head1[u][ch]=cnt;
}
void tarjan(int u)
{
dfn[u]=low[u]=++t;//赋初值
s.push(u);//放入栈中
for (int i=head[u];i;i=edge[i].next)
if (dfn[edge[i].to]==0)
//如果说这个点的dfn为0的话就表示这个点还未被搜索到过
{
tarjan(edge[i].to);
low[u]=min(low[u],low[edge[i].to]);
}
else if (!v[edge[i].to])
//这个点没有出栈的话
low[u]=min(low[u],dfn[edge[i].to]);
if (dfn[u]==low[u])//如果这是一个强连通分量的根的话
{
tot++;//强连通分量数量加1，及缩点后的点数加1
int now=0;
while (now!=u)
{
now=s.top();//弹出栈
s.pop();
v[now]=true;//这个点已经出栈了
node[now]=tot;//这个点属于哪一块强连通分量
size[tot]++; //这个强连通分量的大小加1
}
}
}
void find(int ch)
{
f[node[1]][ch]=size[node[1]];
//ch依旧表示路是否被反向
//f[i][ch]数组则表示在当前的图，1到达[i]的路径上点权和最大为多少
int ta=0;
//当前队列的尾巴
for (int i=1;i<=tot;i++)
if (d[i][ch]==0) q[++ta]=i;//如果说入度为0，加入队列
while (ta>0)//拓扑+dp就不详细解释了
{
int p=q[ta--];
for (int i=head1[p][ch];i;i=edge1[i][ch].next)
{
f[edge1[i][ch].to][ch]=max(f[edge1[i][ch].to][ch],f[p][ch]+size[edge1[i][ch].to]);
if (--d[edge1[i][ch].to][ch]==0) q[++ta]=edge1[i][ch].to;
}
}
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);//连接未缩点之前的边
}
t=0;
for (int i=1;i<=n;i++) if (!v[i]) tarjan(i);
//用tarjan求强连通分量并进行缩点
//v[i]表示这个点有无出栈，如果为false的话，说明这个点还未被访问或者说还在栈中
cnt=0;
for (int i=1;i<=n;i++)
for (int j=head[i];j;j=edge[j].next)
if (node[i]!=node[edge[j].to])//此语句避免自环
{
add1(node[i],node[edge[j].to],1);//连边，之后搜索出的是1能到达的点
add1(node[edge[j].to],node[i],2);//我们反向所有的边，这样搜索出来1能到达的点，其实是能到达1的点，这样就避免了构造n+1这个点
}
memset(f,0xef,sizeof f);//清空为一个很大的负数
find(1);find(2);//搜索
ans=size[node[1]];//开始答案的大小为1所在的强连通分量的大小
for (int i=1;i<=n;i++)
for (int j=head[i];j;j=edge[j].next)
//这里我们枚举所有未缩点前的边（当然这个取决于你自己）
//边的方向本来是node[i]——>node[edge[j].to]
//我们把它们反向，f[node[edge[j].to]][1]表示从点1到node[edge[j].to]，最大点权和为多少
//f[node[i]][2]表示从node[i]到点1最大点权和为多少
//这样边反向后，我们就可以成功的构建一条
//不过因为f[node[edge[j].to]][1]和f[node[i]][2]都包含了1所在的强连通分量的点权，所以我们需要减去一个size[node[1]]。
//1——>node[edge[j].to]——>node[i]——>1的路径了
if (node[i]!=node[edge[j].to])
ans=max(ans,f[node[edge[j].to]][1]+f[node[i]][2]-size[node[1]]);
printf("%d\n",ans);
return 0;
}Catowice City¶
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
vector<int> v[N],w[N],scc[N];
int f[N], g[N], Sc[N];
stack<int> S;
void dfs(int x){
f[x] = 1;
for(int y : v[x]){
if(!f[y]) dfs(y);
}
S.push(x);
}
int c= 0;
void ufs(int x){
g[x] = 1;
scc[c].push_back(x);
Sc[x] = c;
for(int y : w[x])
if(!g[y]) ufs(y);
}
void solve(){
c= 0;
int n, m;
scanf("%d%d", &n, &m);
for(int i =1 ; i <= m; i++){
int a, b;
scanf("%d %d",&a, &b);
v[a].push_back(b+n);
w[b+n].push_back(a);
}
for(int i = 1; i <= n; i++)
v[i+n].push_back(i),
w[i].push_back(i+n);
for(int i = 1; i <= 2*n; i++){
if(f[i] == 0) dfs(i);
}
while(S.size()){
int x = S.top();
S.pop();
if(g[x]) continue;
c++;
ufs(x);
}
for(int i = 1; i <= c; i++){
int fl = 1,a=0,b=0;
for(int j : scc[i]){
if(j <= n) a++;
else b++;
for(int x : v[j])
if(Sc[x] != i) fl = 0;
}
if(!fl || a != b || scc[i].size() == 2*n || scc[i].size()==0) continue;
cout<<"Yes\n";
printf("%d %d\n",scc[i].size()/2,n - scc[i].size()/2);
for(int j = 1; j <= n; j++)
if(Sc[j] == i) printf("%d ", j);
cout<<endl;
for(int j = 1; j <= n; j++)
if(Sc[j+n] != i) printf("%d ", j);
cout<<endl;
for(int i = 1; i <= 2*n; i++)
v[i].clear(), w[i].clear(), scc[i].clear(),f[i] =0,g[i] = 0,Sc[i] =0;
return;
}
cout<<"No"<<endl;
for(int i = 1; i <= 2*n; i++)
v[i].clear(), w[i].clear(), scc[i].clear(),f[i] =0,g[i] = 0,Sc[i] =0;
}
main(){
int T;
cin >> T;
while(T--){
solve();
}
}Festival¶
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 605;
struct edge {
int next,to;
}a[N * 100];
int head[N],dis[N][N],maxn[N],n,m1,m2,a_size = 1,ans = 0;
inline void add(int u,int v) {
a[++a_size] = (edge){head[u],v};
head[u] = a_size;
}
int dfn[N],low[N],sta[N],c[N],top = 0,cnt = 0,num = 0;
bool ins[N];
void tarjan(int x) {
dfn[x] = low[x] = ++num;
sta[++top] = x,ins[x] = true;
for(int i = head[x]; i; i = a[i].next) {
int y = a[i].to;
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
}
else if(ins[y])
low[x] = min(low[x],dfn[y]);
}
if(dfn[x] == low[x]) {
cnt++; int y; do {
y = sta[top--]; ins[y] = false;
c[y] = cnt;
}while(y != x);
}
}
inline int read() {
int x = 0,flag = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')flag = -1;ch = getchar();}
while(ch >='0' && ch <='9'){x = (x << 3) + (x << 1) + ch - 48;ch = getchar();}
return x * flag;
}
int main() {
memset(dis,0x3f,sizeof(dis));
n = read(),m1 = read(),m2 = read();
for(int i = 1; i <= n; i++) dis[i][i] = 0;
for(int i = 1; i <= m1; i++) {
int u = read(),v = read();
add(u,v); add(v,u);
dis[u][v] = min(dis[u][v],-1);
dis[v][u] = min(dis[v][u],1);
}
for(int i = 1; i <= m2; i++) {
int u = read(),v = read();
add(u,v);
dis[u][v] = min(dis[u][v],0);
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
if(c[i] != c[k]) continue;
for(int j = 1; j <= n; j++) {
if(c[j] != c[i]) continue;
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
}
}
}
for(int i = 1; i <= n; i++)
if(dis[i][i]) {
puts("NIE");
return 0;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(c[j] != c[i]) continue;
maxn[c[i]] = max(maxn[c[i]],dis[i][j]);
}
}
for(int i = 1; i <= cnt; i++) ans += maxn[i] + 1;
printf("%d",ans);
return 0;
}
最后更新:
2023-01-31