圖論水題日記

cf1805D

題意

給定一棵樹，規定 $\geq k$ 時 $(u, v)$ 之間存在一條無向邊，求 $k = (1, 2, ... n)$ 時圖中的連通塊個數

思路

前置知識：樹上一點到其最遠的點一定是樹直徑的兩個端點之一
若一個點到其最遠的點大于k，那么其一定是孤立點，我們可以計算出每個點在k為多少時變成孤立點，答案即為前綴和
所以計算出直徑兩端點之后再計算出所有點到兩端點的距離，則i點在 $k = ma x (d i s 1 [i], d i s 2 [i]) + 1$ 時變成孤立點
需要注意k=0時，連通塊為1個，k>直徑時，所有點都孤立，即n個連通塊

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  const int N=1e5+10;
vector<int>e[N];void solve()
{int n;cin>>n;for(int i=1;i<n;i++){int a,b;cin>>a>>b;e[a].pb(b);e[b].pb(a);}vector<int>dep(n+1,-1);int root1,root2;int deepest=1;auto dfs=[&](auto && dfs,int u,int fa)->void{dep[u]=dep[fa]+1;if(dep[u]>dep[deepest]) deepest=u;for(auto ed:e[u]){if(ed==fa) continue;dfs(dfs,ed,u);}};dfs(dfs,1,0);root1=deepest;dfs(dfs,root1,0);root2=deepest;auto dfs1=[&](auto && dfs1,vector<int>&dis,int u,int fa)->void{dis[u]=dis[fa]+1;for(auto ed:e[u]){if(ed==fa) continue;dfs1(dfs1,dis,ed,u);}};vector<int>dis1(n+1,-1);dis1[root1]=0;dfs1(dfs1,dis1,root1,0);vector<int>dis2(n+1,-1);dis2[root2]=0;dfs1(dfs1,dis2,root2,0);//cout<<root1<<" "<<root2<<endl;//for(int i=1;i<=n;i++) cout<<dis1[i]<<" "<<dis2[i]<<endl;vector<int>ans(n+1);//k為i時增加孤點數for(int i=1;i<=n;i++) ans[max(dis1[i],dis2[i])+1]++;ans[0]=1;for(int i=1;i<=n;i++){ans[i]+=ans[i-1];cout<<(i>dep[root2] ? n : ans[i])<<" \n"[i==n];}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf1775D

題意

給定n個節點，若 $gcd(a_i,a_j)!=1$ 則 $a_i,a_j$ 之間存在一條無向邊，且所有邊權都為1，給定兩點，求這兩點的最短路上的節點個數已經路徑

$\leq n \leq 3 \cdot 10^5$
$\leq a_i \leq 3 \cdot 10^5$

思路

考慮暴力做法,枚舉所有 $i, j$ 對其求gcd后建邊后跑最短路，則時間復雜度是 $O(n^2log)$ 不肯通過，考慮優化發現所有具備同一個因數的點都會連一條邊，不妨將每個因數建立虛點，將所有包含此因數的點對其連邊建圖，這樣做時間復雜度為 $\sqrt n)$ ,但實際上我們只需要關注質因數即可，兩個不互質的數一定有共同的質因數，這樣時間復雜度為 $O (n l o g n)$
具體做法為對于所有 $a_i$ 分解質因數，然后將其與質因數連邊，一條邊權為1的出邊，一條邊權為0的入邊，然后跑dij求最短路即可

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  const int N=3e5+10;
struct edge{int v,w;
};
vector<edge>e[N<<1];void solve()
{int n;cin>>n;vector<int>a(n+1);for(int i=1;i<=n;i++) cin>>a[i];int st,ed;cin>>st>>ed;for(int i=1;i<=n;i++){int x=a[i];for(int j=2;j*j<=x;j++){if(x%j==0){while(x%j==0) x/=j;e[i].pb({j+N,1});e[j+N].pb({i,0});}}if(x!=1){e[i].pb({x+N,1});e[x+N].pb({i,0});}}priority_queue<PII,vector<PII>,greater<PII>>q;vector<int>dis(N<<1,inf);dis[st]=0;q.push({0,st});vector<int>vis(N<<1);map<int,int>last;while(!q.empty()){auto [cost,cur]=q.top();q.pop();if(vis[cur]) continue;vis[cur]=1;for(auto [v,w]:e[cur]){if(cost+w<dis[v]){last[v]=cur;dis[v]=cost+w;q.push({dis[v],v});}}}if(dis[ed]==inf) {cout<<-1<<endl;return;}vector<int>path;auto dfs=[&](auto &&dfs,int u)->void{if(u<N) path.pb(u);if(u==st) return;dfs(dfs,last[u]);};dfs(dfs,ed);reverse(all0(path));cout<<path.size()<<endl;for(auto t:path) cout<<t<<" ";
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf118E

題意

給定一張 $n$ 個點, $m$ 條邊的無向圖，是否存在一種將其變為有向圖的方法，使該圖是一個強連通分量

思路

若圖中存在割邊則一定無解，使用tarjan判斷圖中是否有割邊，可以發現有向邊的構造方法恰為tarjan的訪問順序

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  const int N=2e6+10;
vector<int>head(N,-1);
int idx=0;
struct edge{int to,next;
}e[N];int cnt;
int low[N],dfn[N],tot;
vector<PII>ans;void add(int u,int v)
{e[idx].to=v;e[idx].next=head[u];head[u]=idx++;
}void tarjan(int x,int fa)
{low[x]=dfn[x]=++tot;for(int i=head[x];~i;i=e[i].next){int y=e[i].to;if(y==fa) continue;if(!dfn[y]){tarjan(y,x);low[x]=min(low[x],low[y]);ans.pb({x,y});if(low[y]>dfn[x]) cnt++;}else if(dfn[y]<dfn[x]){low[x]=min(low[x],dfn[y]);ans.pb({x,y});}}
}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;add(a,b);add(b,a);}tarjan(1,0);if(cnt) {cout<<0<<endl;return;}for(auto [x,y]:ans){cout<<x<<" "<<y<<endl;}}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf999E

題意

$n$ 個點， $m$ 條邊的有向圖，如果要滿足點 $s$ 可以到達所有點，需要添加幾條邊

思路

對于一個強連通分量內的點只要可以到達其中一個，那么全部都可達
觀察樣例可以發現答案即為縮點后入度為0的點的個數
但需要注意s點所在連通塊不納入計算

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  const int N=5010;
vector<int>e[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;vector<int>e1[N];void tarjan(int x)
{dfn[x]=low[x]=++tot;stk[++top]=x;instk[x]=1;for(auto ed:e[x]){if(!dfn[ed]){tarjan(ed);low[x]=min(low[x],low[ed]);}else if(instk[ed]){low[x]=min(low[x],dfn[ed]);}}if(dfn[x]==low[x]){int y;cnt++;do{y=stk[top--];instk[y]=0;scc[y]=cnt;++siz[cnt];}while(y!=x);}
}void solve()
{int n,m,s;cin>>n>>m>>s;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;e[a].pb(b);}for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}//cout<<cnt<<endl;vector<int>din(n+1);for(int i=1;i<=n;i++){for(auto ed:e[i]){if(scc[ed]!=scc[i]){e1[scc[i]].pb(scc[ed]);din[scc[ed]]++;}}}int ans=0;vector<int>st(n+1);for(int i=1;i<=cnt;i++){if(i==scc[s]) continue;if(!din[i]){if(!st[i]) ans++;st[i]=1;}}cout<<ans<<endl;}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf25c

題意

給定 $n$ 個點的最短距離矩陣 $\leq n \leq 300)$ ,以及k條路徑，代表新建一條 $a$ 到 $b$ 邊權為 $c$ 的路徑，求每次新建路徑之后所有點對的最短路之和

思路

由數據范圍不難想到floyd,若每次新建路徑邊權小于之前的邊權，就嘗試對所有經過 $a, b$ 點和 $b, a$ 點的最短路徑進行更新

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  void solve()
{int n;cin>>n;vector<vector<ll>>dis(n+1,vector<ll>(n+1));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cin>>dis[i][j];}ll ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++) ans+=dis[i][j];}int m;cin>>m;while(m--){ll a,b,c;cin>>a>>b>>c;if(c>=dis[a][b]) {cout<<ans<<" ";continue;}dis[a][b]=dis[b][a]=c;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) continue;dis[i][j]=min(dis[i][j],dis[i][a]+dis[a][b]+dis[b][j]);dis[i][j]=min(dis[i][j],dis[i][b]+dis[b][a]+dis[a][j]);}}ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++) ans+=dis[i][j];}cout<<ans<<" ";}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf1272E

題意

給定n個元素的數組，若 $i+ai≤ni+a_i \leq n$ 則 $i$ 與 $i+a_i$ 之間存在一條代價為1的邊，若 $i?ai≥1i-a_i \geq 1$ 則則 $i$ 與 $i-a_i$ 之間存在一條代價為1的邊，對于每個 $a_i$ 求到達與其奇偶性不同的點的最小步數

思路

考慮多源bfs，要求解偶數點到奇數點的最小步數，從所有奇數點出發，走反邊跑bfs，奇數點到偶數點同理，相反即可

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  const int N=2e5+10;vector<int>e[N];void solve()
{int n;cin>>n;vector<int>a(n+1);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){if(i+a[i]<=n) e[i+a[i]].pb(i);if(i-a[i]>=1) e[i-a[i]].pb(i);}vector<int>ans(n+1,-1),dis(n+1,1e9);queue<int>q;auto bfs=[&](){while(!q.empty()){auto t=q.front();q.pop();for(auto ed:e[t]){if(dis[t]+1<dis[ed]){dis[ed]=dis[t]+1;q.push(ed);}}}};for(int i=1;i<=n;i++){if(a[i]%2==0){q.push(i);dis[i]=0;}}bfs();for(int i=1;i<=n;i++){if(a[i]&1) ans[i]=dis[i];}fill(all(dis),1e9);for(int i=1;i<=n;i++){if(a[i]%2){q.push(i);dis[i]=0;}}bfs();for(int i=1;i<=n;i++){if(a[i]%2==0) ans[i]=dis[i];}for(int i=1;i<=n;i++) cout<<(ans[i]==1e9?-1:ans[i])<<" \n"[i==n];}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf1872F

題意

$n$ 個動物，其害怕的動物為 $a_i$ ,其價值為 $c_i$ ，如果一個動物被賣出時其害怕的動物還沒有被賣出，則可以得到 $2*c_i$ 的收益，反之得到 $c_i$ 的收益，求一個排列代表可以獲得最大收益的賣出動物的順序

思路

我們把每個點向其害怕的點連一條出邊，由于有n個點n條邊，且每個點只有一條出邊，所以圖中必定有環，不難發現對于不在環內的點按拓撲序賣出更優，而對于在環內的點，貪心的想一定最后賣 $c_i$ 最小的點，這樣環上的其他點都能得到 $2*c_i$ 的收益

這題顯然用拓撲排序做更快，自己用tarjan搞了半天，其實tarjan有一個很重要的性質，其scc出棧的順序就是逆拓撲序，所以我們可以找到環上價值最小的點，將其加入答案數組中，由于這樣做為逆拓撲排序，最后reverse輸出即可

代碼

#include<bits/stdc++.h>#define ull unsigned long long 
#define ll long long
#define inf 1e9
#define INF 1e18
#define lc p<<1
#define rc p<<1|1
#define endl '\n'
#define all(a) a.begin()+1,a.end()
#define all0(a) a.begin(),a.end()
#define lowbit(a) (a&-a)
#define fi first
#define se second
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endlusing namespace std;
const double eps=1e-6;
typedef pair<int,int>PII;
typedef array<int,3>PIII;
mt19937_64 rnd(time(0));  const int N=1e5+10;
vector<int>e[N];int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;int c[N];vector<int>ans;void tarjan(int x)
{dfn[x]=low[x]=++tot;stk[++top]=x;instk[x]=1;for(auto ed:e[x]){if(!dfn[ed]){tarjan(ed);low[x]=min(low[x],low[ed]);}else if(instk[ed]){low[x]=min(low[x],dfn[ed]);}}if(dfn[x]==low[x]){int y;++cnt;vector<int>circle;do{y=stk[top--];instk[y]=0;circle.pb(y);scc[y]=cnt;++siz[cnt];//cout<<y<<endl;}while(y!=x);int len=circle.size();int mn=1e9;for(auto x:circle) mn=min(mn,c[x]);int pos=-1;for(int i=0;i<len;i++) if(c[circle[i]]==mn) {pos=i;break;}for(int i=pos;i<len;i++) ans.pb(circle[i]);for(int i=0;i<pos;i++) ans.pb(circle[i]);}}void solve()
{int n;cin>>n;for(int i=1;i<=n;i++){dfn[i]=low[i]=0;stk[i]=instk[i]=0;scc[i]=siz[i]=0;tot=top=cnt=0;c[i]=0;ans.clear();e[i].clear();}for(int i=1;i<=n;i++){int x;cin>>x;e[i].pb(x);}for(int i=1;i<=n;i++) cin>>c[i];for(int i=1;i<=n;i++){if(!dfn[i]) tarjan(i);}reverse(all0(ans));for(auto t:ans) cout<<t<<" ";cout<<endl;}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();return 0;
}