Tarjan Shrinking Points can shrink each strongly connected component of a graph into a point and then construct a new graph, which becomes a directed acyclic graph. After it becomes a directed acyclic graph it can be combined with the shortest circuit, topology ...... Solve the corresponding topic
Rocky Valley Questionnaire Share:
/training/526565
The first few are green questions, nothing to write home about, roughly go through them
1. Strongly connected components
Title Link:/problem/B3609
Problem: find every strongly connected component, too templated
AC Code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e4+10;
vector<int> e[N].
int dfn[N],low[N],tot,a[N];//dfn[x] is the order in which the nodes were first visited (timestamp), low[x] is the earliest timestamp that can be accessed from node x
int stk[N],instk[N],top;// mark whether it is in the stack or not
int scc[N],siz[N],cnt;//scc[x] counts which strongly connected component x is in
void tarjan(int x) {
//stamp and stack when entering x
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {// if y has not been accessed yet
tarjan(y);
low[x] = min(low[x], low[y]); //update low when going back to x
} else if (instk[y])//if y is visited and on the stack
low[x] = min(low[x], dfn[y]);//update low on x
}
// collect SCC when away from x
if (dfn[x] == low[x]) {// if x is the root of the SCC
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCC numbering
siz[cnt] += a[y];//SCC size
} while (y ! = x);
}
}
int st[N];
void solve() {
int n, m; cin >> n >> m; }
cin >> n >> m; for (int i = 1; i <= m; i++) { int st[N]; void solve()
for (int i = 1; i <= m; i++) {
int u, v; cin >>
cin >> u >> v.
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
cout << cnt << endl;
vector<int> ans[N].
for (int i = 1; i <= n; i++) {// This directly satisfies the numbering of nodes in each strongly connected component from small to large
ans[scc[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {
for (auto k: ans[scc[i]]) {
st[k] = 1;
cout << k << " ";;
}
cout << endl.
}
}
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;; cin
// cin >> t;
// while (t--)
solve(); // return 0; return 0; // t; // cin >>
return 0; // t; // cin >> // while (t--)
}
Cow Prom S
Title Link:/problem/P2863
Template questions, put the code directly
#include<bits/stdc++.h>
#define int long long
using namespace std.
const int N=1e5+10.
int n,m,a,b; vector<int>
vector<int> e[N].
int dfn[N],low[N],tot;//dfn[x] is the order in which the nodes were first visited (timestamp), low[x] is the earliest timestamp that can be accessed from node x
int stk[N],instk[N],top;// mark whether it is in the stack or not
int scc[N],siz[N],cnt;//scc[x] counts which strongly connected component x is in
void tarjan(int x) {
//stamp and stack when entering x
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {// if y has not been accessed yet
tarjan(y);
low[x] = min(low[x], low[y]); //update low when going back to x
} else if (instk[y])//if y is visited and on the stack
low[x] = min(low[x], dfn[y]);//update low on x
}
// collect SCC when away from x
if (dfn[x] == low[x]) {// if x is the root of the SCC
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCC numbering
++siz[cnt];//SCC size
} while (y ! = x);
}
}
signed main() {
cin >> n >> m; cin >> n >> m; while (m--)
while (m--)
cin >> a >> b, e[a].push_back(b);
for (int i = 1; i <= n; i++)//may not be connected
if (!dfn[i]) tarjan(i);
int ans = 0;
for (int i = 1; i <= cnt; i++)
if (siz[i] >1) ans++;
cout << ans << endl.
cout << ans << endl; return 0;
}
3. Popular Cattle
Title Link:/problem/P2341
If there is more than one strongly connected component with out-degree 0, then the number of popular cows is 0. Otherwise, the number of popular cows is the number of cows in that strongly connected component
AC Code:
#include<bits/stdc++.h>
#define int long long
using namespace std.
const int N=1e5+10.
int n,m; vector<int>
vector<int> e[N].
int dfn[N],low[N],tot;//dfn[x] is the order in which the nodes were first visited (timestamp), low[x] is the earliest timestamp that can be accessed from node x
int stk[N],instk[N],top;// mark whether it is in the stack or not
int scc[N],siz[N],cnt;//scc[x] counts which strongly connected component x is in
int din[N],dout[N];
void tarjan(int x) {
// stamp and stack when entering x
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {// if y has not been accessed yet
tarjan(y);
low[x] = min(low[x], low[y]); //update low when going back to x
} else if (instk[y])//if y is visited and on the stack
low[x] = min(low[x], dfn[y]);//update low on x
}
// collect SCC when away from x
if (dfn[x] == low[x]) {// if x is the root of the SCC
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCC numbering
++siz[cnt];//SCC size
} while (y ! = x);
}
}
signed main() {
cin >> n>>m; for (int i = 1; i <= m; i++) {
for (int i = 1; i <= m; i++) {
int u,v; cin>>
cin>>u>>v.
e[u].push_back(v);
}
for (int i = 1; i <= n; i++)//may not be connected
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {// scc shrinks the connected component to a point
for (auto k: e[i]) {
if (scc[i] ! = scc[k]) {
dout[scc[i]]++;
din[scc[k]]++;
}
}
}
int ans,num=0;
for (int i = 1; i <= cnt; i++) {
if (!dout[i]) ans+=siz[i],num++;
}
if(num==1) cout<<ans<<endl;
else cout<<0<<endl;
cout<<ans<<endl; else
}
4. [Template] Shrink Point
Title Link:/problem/P3387
Topology + Shrinking Points
AC Code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e4+10;
vector<int> e[N];
int dfn[N],low[N],tot,a[N];//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
siz[cnt] += a[y];//SCCadults and children
} while (y != x);
}
}
vector<int> ne[N];
int din[N],sum[N];
int topo(){
queue<int> q;
for(int i=1;i<=cnt;i++){
if(!din[i]) (i),sum[i]=siz[i];
}
while(()){
int u=();
();
for(auto v:ne[u]){
sum[v]=max(sum[v],siz[v]+sum[u]);
--din[v];
if(din[v]==0) (v);
}
}
int ans=0;
for(int i=1;i<=cnt;i++){
ans=max(ans,sum[i]);
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
e[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: e[u]) {
if (scc[v] == scc[u]) continue;
ne[scc[u]].push_back(scc[v]);
din[scc[v]]++;
}
}
cout<<topo()<<endl;
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
5. Kamishirasawa Keine
Title Link:/problem/P1726
template question
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e4+10;
vector<int> e[N];
int dfn[N],low[N],tot;//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
siz[cnt] ++;//SCCadults and children
} while (y != x);
}
}
void solve() {
int n, m;
cin >> n >> m;
int x, u, v;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> x;
if (x == 1) {
e[u].push_back(v);
} else {
e[u].push_back(v);
e[v].push_back(u);
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
vector<int> ans[N];
for (int i = 1; i <= n; i++) {
ans[scc[i]].push_back(i);
}
int ans1 = 0;
for (int i = 1; i <= cnt; i++) {
ans1 = max(ans1, siz[i]);
}
cout << ans1 << endl;
for (int i = 1; i <= cnt; i++) {
if (siz[i] == ans1) {
for (auto k: ans[i]) {
cout << k << " ";
}
cout << endl;
}
}
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
5. Proliferation of information
Title Link:/problem/P2002
The answer is the number of indentation points with zero incidence.
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
vector<int> e[N];
int dfn[N],low[N],tot;//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
siz[cnt] ++;//SCCadults and children
} while (y != x);
}
}
int din[N];
void solve() {
int n, m;
cin >> n >> m;
int u, v;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
if (u != v) e[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: e[u]) {
if (scc[u] == scc[v]) continue;
din[scc[v]]++;
}
}
int pp = 0;
for (int i = 1; i <= cnt; i++) {
if (!din[i]) pp++;
}
cout << pp << endl;
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
Next up are a couple of blue questions
P1262 Espionage networks
Title Link:/problem/P1262
First of all, how to judge can control all the spies it (that is, to judge Yes or No), shrink the point to build a new map, if the degree of entry is 0 and the degree of entry of 0 in the strong connectivity component of all the points can not be controlled, so that there will be spies can not be controlled, on the output of the No. Output YES behind the smallest bribe to be paid, on the degree of entry of 0 in the strong connectivity component of the smallest amount of each point to be added up! Just do it.
The last thing is the output behind No. Using the topology (in the topology, the points that are deposited into the queue first are the strongly connected components that can be controlled), the strongly connected components that cannot be controlled are solved for, and then the smallest one is taken.
AC Code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
vector<int> e[N];
int dfn[N],low[N],tot,a[N];//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
int din[N];
int n, p;
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
siz[cnt] ++;//SCCadults and children
} while (y != x);
}
}
vector<int> ans[N];
vector<int> ne[N];
int book[N],st[N];
int topo(){
int t=1e18;
queue<int> q;
for(int i=1;i<=cnt;i++){
if(book[i]) (i),st[i]=1;
}
while(()){
int k=();
();
for(auto v:ne[k]){
din[v]--;
if(din[v]==0){
(v);
st[v]=1;
}
}
}
for(int i=1;i<=cnt;i++){
if(!st[i]){
t=min(t,ans[i][0]);
}
}
return t;
}
void solve() {
cin >> n >> p;
for (int i = 1; i <= p; i++) {
int x, w;
cin >> x >> w;
a[x] = w;
}
int r;
cin >> r;
while (r--) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {
ans[scc[i]].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (a[i]) {
book[scc[i]] = 1;
}
}
for (int u = 1; u <= n; u++) {
for (int v: e[u]) {
if (scc[v] != scc[u]) {
din[scc[v]]++;
ne[scc[u]].push_back(scc[v]);
}
}
}
int ans1 = 0;
int fl = 0;
for (int i = 1; i <= cnt; i++) {
if (din[i] == 0) {
int mn = 1e18, f = 0;
for (auto k: ans[i]) {
if (!a[k]) continue;
else {
f = 1;
mn = min(mn, a[k]);
}
}
if (f) {
ans1 += mn;
} else {
fl = 1;
}
}
}
if (fl) {
cout << "NO" << endl;
cout << topo() << endl;
} else {
cout << "YES" << endl;
cout << ans1 << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
P2169 Regular Expressions
Title Link:/problem/P2169
This question is the shortest circuit after shrinking the point, it's very simple
AC Code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
struct node{
int v,w;
};
vector<node> e[N];
int dfn[N],low[N],tot,a[N];//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
int din[N];
int n, m;
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (auto k: e[x]) {
int y=;
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
siz[cnt] ++;//SCCadults and children
} while (y != x);
}
}
vector<node> ne[N];
struct node1 {
int x, y;
};
struct cmp {bool operator()(const node1 &a, const node1 &b) const {return > ;}};
priority_queue<node1,vector<node1>,cmp> q;
int d[N],vis[N];
void dj(int s) {
for (int i = 1; i <= cnt; i++) {
d[i] = inf;
}
d[s] = 0;
({0, s});
while (()) {
auto t = ();
();
int u = ;
if (vis[u]) continue;
vis[u] = 1;
for (auto k: ne[u]) {
int v = , w = ;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
({d[v], v});
}
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back({v, w});
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; u++) {
for (auto k: e[u]) {
int v = , w = ;
if (scc[u] != scc[v]) {
ne[scc[u]].push_back({scc[v], w});
}
}
}
dj(scc[1]);
cout << d[scc[n]] << endl;
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
P2194 HXY Burning Couple
Title Link:/problem/P2194
The minimum spend then finds the amount of gasoline at the smallest point in each strongly connected component, and the number of schemes is the product of the smallest number in each strongly connected component
AC Code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f,mod=1e9+7;
vector<int> e[N];
int dfn[N],low[N],tot,a[N];//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
int din[N];
int n, m;
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
// siz[cnt]++;
siz[cnt] =min(siz[cnt],a[y]);//SCCadults and children
} while (y != x);
}
}
vector<int> ne[N];
vector<int> ans[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
siz[i] = 1e9;
}
cin >> m;
while (m--) {
int u, v;
cin >> u >> v;
e[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: e[u]) {
if (scc[u] != scc[v]) {
din[scc[v]]++;
}
}
}
for (int i = 1; i <= n; i++) {
ans[scc[i]].push_back(i);
}
int ans1 = 0;
int ans2 = 1;
for (int i = 1; i <= cnt; i++) {
ans1 += siz[i];
int t = 0;
for (auto k: ans[i]) {
if (a[k] == siz[i]) t++;
}
ans2 = ((ans2 % mod) * (t % mod)) % mod;
}
cout << ans1 << " " << ans2 << endl;
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
P2812 Network of Schools [[USACO] Network of Schools Enhanced Edition
Title Link:/problem/P2812
The first line, an integer, indicates that the selection of at least a few schools as shareware motherships will enable each school to have access to it. After indentation, that is, the number of entries with degree 0
The second line is an integer that indicates the minimum number of lines that must be added to enable any school to use the software as the mother computer for any other school. That is, max (the number of lines with 0 in and 0 out).
Note that you have to special-case the number of strongly connected components to be 1
AC Code:
#include<bits/stdc++.h>
#define int long long
using namespace std.
const int N=1e5+10.
int n,m; vector<int>
vector<int> e[N].
int dfn[N],low[N],tot;//dfn[x] is the order in which the nodes were first visited (timestamp), low[x] is the earliest timestamp that can be accessed from node x
int stk[N],instk[N],top;// mark whether it is in the stack or not
int scc[N],siz[N],cnt;//scc[x] counts which strongly connected component x is in
int din[N],dout[N];
void tarjan(int x) {
// stamp and stack when entering x
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {// if y has not been accessed yet
tarjan(y);
low[x] = min(low[x], low[y]); //update low when going back to x
} else if (instk[y])//if y is visited and on the stack
low[x] = min(low[x], dfn[y]);//update low on x
}
// collect SCC when away from x
if (dfn[x] == low[x]) {// if x is the root of the SCC
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCC numbering
++siz[cnt];//SCC size
} while (y ! = x);
}
}
signed main() {
cin >> n; for(int i=1;i<=n;i++){
for(int i=1;i<=n;i++){
while(1){
cin>>m;
if(m==0){
m; if(m==0){ break;
}
e[i].push_back(m);
}
}
for (int i = 1; i <= n; i++)//may not be connected
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++){//scc indentation point
for(auto k:e[i]){
if(scc[i]! =scc[k]){
dout[scc[i]]++;
din[scc[k]]++;
}
}
}
int a,b=0;
for(int i=1;i<=cnt;i++){
if(!din[i]) a++;
if(!dout[i]) b++;
}
if(cnt==1){
cout<<1<<endl<<0<<endl;
}
endl; }
cout<<a<<endl<<max(a,b)<<endl;
endl; endl; endl; max(a,b)<<return 0;
}
P3627 [APIO2009] Looting Programs
Title Link:/problem/P3627
The general purpose of the topic: to run a longest way after a point reduction
First of all this is entitled point-weighted graph, so first turn the point-weights into edge-weights, then turn the edge-weights into negative numbers, and run the shortest path with spfa to find the longest path
AC Code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f,mod=1e9+7;
struct node{
int v,w;
};
vector<int> e[N];
int dfn[N],low[N],tot,a[N];//dfn[x]is the order in which the nodes were first accessed（timestamp），low[x]slave nodex出发能访问的最早timestamp
int stk[N],instk[N],top;//Whether the marker is on the stack
int scc[N],siz[N],cnt;//scc[x]creditxIn which strongly connected component
int din[N];
int n, m, tmp;
void tarjan(int x) {
//confirm or agree withxhour，postmark、confirm or agree with栈
dfn[x] = low[x] = ++tot;
stk[++top] = x, instk[x] = 1;
for (int y: e[x]) {
if (!dfn[y]) {//asyNot yet visited
tarjan(y);
low[x] = min(low[x], low[y]);//classifier for a chapter in old Chinese fictional novelsxhour更新low
} else if (instk[y])//asyVisited and on the stack
low[x] = min(low[x], dfn[y]);//existxhour更新low
}
//mythical beast (archaic)xhour，collectsSCC
if (dfn[x] == low[x]) {//asxbeSCCroot of an equation
int y;
++cnt;
do {
y = stk[top--];
instk[y] = 0;
scc[y] = cnt;//SCCserial number
siz[cnt] += a[y];//SCCadults and children
} while (y != x);
}
}
vector<int> ans[N];
vector<node> ne[N];
int ed[N],d[N],vis[N];
queue<int> q;
void spfa(int s) {
for (int i = 1; i <= tmp; i++) {
d[i] = inf;
}
d[s] = 0;
vis[s] = 1;
(s);
while (()) {
int u = ();
();
vis[u] = 0;
for (auto k: ne[u]) {
int v = , w = ;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (!vis[v]) (v), vis[v] = 1;
}
}
}
}
void solve() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] = -1 * a[i];
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; u++) {
for (int v: e[u]) {
if (scc[u] != scc[v]) {
ne[scc[u]].push_back({scc[v], siz[scc[u]]});
}
}
}
int s, p;
cin >> s >> p;
tmp = cnt;
for (int i = 1; i <= p; i++) {
cin >> ed[i];
ne[scc[ed[i]]].push_back({++tmp, siz[scc[ed[i]]]});
}
spfa(scc[s]);
int ans1 = 0;
for (int i = cnt + 1; i <= tmp; i++) {
ans1 = max(-1 * d[i], ans1);
}
cout << ans1 << endl;
}
signed main() {
ios_base::sync_with_stdio(0), (0), (0);
// int t;
// cin >> t;
// while (t--)
solve();
return 0;
}
The next little bit of questions are just going to be done later when I'm bored, now it's time to brush up on Tarjan cut points.