当前位置：首页 > news >正文

图论水题4

news 2025/8/18 7:33:28

cf920E

题意

给定一张n个点m条边的无向图，求其补图的连通块个数以及每个连通块的大小

思路

暴力，每个点只可能在一个连通块内，用一个队列维护当前还没有被确定连通块的点，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"<<endl
#define i128 __int128using 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;
set<int>s[N];void solve()
{int n,m;cin>>n>>m;queue<int>q;for(int i=1;i<=n;i++) q.push(i);for(int i=1;i<=m;i++){int a,b;cin>>a>>b;s[a].insert(b);}vector<int>vis(n+1);vector<int>ans(n+1);int cnt=1;auto bfs=[&](int x){queue<int>q1;q1.push(x);while(!q1.empty()){auto t=q1.front();q1.pop();int len=q.size();for(int i=1;i<=len;i++){auto u=q.front();q.pop();if(!s[t].count(u) && !s[u].count(t)){ans[cnt]++;vis[u]=1;q1.push(u);}else q.push(u);}}};for(int i=1;i<=n;i++){if(vis[i]) continue;vis[i]=1;bfs(i);cnt++;}sort(ans.begin()+1,ans.begin()+cnt);cout<<cnt-1<<endl;for(int i=1;i<cnt;i++) cout<<ans[i]<<" ";}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf1517D

题意

给一个最多 $500 * 500$ 的四联通加权网格图,求从每一个点出发走k步最后回到这个点的最小边权和， $\leq k \leq 20$

思路

k为奇数时一定无解
k为偶数时一定是向外先走 $k2\frac{k}{2}$ ，再走回来更优
问题变成从一个点出发走 $k2\frac{k}{2}$ 步的最小代价
考虑dp求解即可

代码

#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"<<endl
#define i128 __int128using 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=510;
int dp[N][N][22];void solve()
{int n,m,k;cin>>n>>m>>k;vector<vector<int>>roww(n+1,vector<int>(m+1));auto colw=roww;for(int i=1;i<=n;i++){for(int j=1;j<m;j++) cin>>colw[i][j];}for(int i=1;i<n;i++){for(int j=1;j<=m;j++) cin>>roww[i][j];}if(k&1){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) cout<<-1<<" ";cout<<endl;}return;}for(int s=1;s<=k;s++){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j][s]=inf;if(i>1) dp[i][j][s]=min(dp[i][j][s],dp[i-1][j][s-1]+roww[i-1][j]);if(i<n) dp[i][j][s]=min(dp[i][j][s],dp[i+1][j][s-1]+roww[i][j]);if(j>1) dp[i][j][s]=min(dp[i][j][s],dp[i][j-1][s-1]+colw[i][j-1]);if(j<m) dp[i][j][s]=min(dp[i][j][s],dp[i][j+1][s-1]+colw[i][j]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) cout<<dp[i][j][k>>1]*2<<" ";cout<<endl;}}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf1095F

题意

有一张n个点的完全图，每个点有一个点值w，点 $x, y$ 的边权为 $w_x+w_y$ ，另外给出m条边，求这张图的最小生成树

思路

完全图直接跑kruskal显然不可取，kruskal每次只关心边权最小的边，由于该图边权的性质，可以发现一定是其他点向点权最小的点连边最优，即以最小点权为中心点的菊花图，那么对于其余的m条边可以直接加入，然后跑kruskal即可

代码

#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"<<endl
#define i128 __int128using 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;
struct edge{ll u,v,w;bool operator <(const edge&t)const{return w<t.w;}
};
int p[N];int find(int x)
{if(x!=p[x]) p[x]=find(p[x]);return p[x];
}void merge(int x,int y)
{x=find(x);y=find(y);if(x!=y) p[x]=y;
}void solve()
{int n,m;cin>>n>>m;vector<ll>w(n+1);int root=1;for(int i=1;i<=n;i++){p[i]=i;cin>>w[i];if(w[i]<w[root]) root=i; }vector<edge>e;for(int i=1;i<=n;i++){if(i==root) continue;e.pb({root,i,w[root]+w[i]});}for(int i=1;i<=m;i++){ll a,b,c;cin>>a>>b>>c;e.pb({a,b,c});}sort(all0(e));ll ans=0;int cnt=0;for(auto [u,v,w]:e){u=find(u);v=find(v);if(u!=v){merge(u,v);ans+=w;cnt++;}if(cnt==n-1) break;}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf 463D

题意

给定m个长度为n的排列，求最长公共子序列 $\leq n \leq n$
$1≤m≤51\leq m \leq 5$

思路

如果m个排列中的j都出现在i的右边，那么说明i可以到达j，此时可以对i连接一条到j的边，对每个点求最长路即可，连边的复杂度为 $O(n^2m)$

代码

#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"<<endl
#define i128 __int128using 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=1010;
vector<int>e[N];void solve()
{int n,m;cin>>n>>m;vector<vector<int>>a(m+1,vector<int>(n+1));auto pos=a;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];pos[i][a[i][j]]=j;}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) continue;int ok=1;for(int k=1;k<=m;k++){if(pos[k][j]<pos[k][i]) {ok=0;break;}}if(ok) e[i].pb(j);}}int ans=0;vector<int>dp(n+1,-1);auto dfs=[&](auto &&dfs,int u)->int{if(dp[u]!=-1) return dp[u];dp[u]=1;for(auto ed:e[u]) dp[u]=max(dp[u],dfs(dfs,ed)+1);return dp[u];};for(int i=1;i<=n;i++){if(dp[i]==-1) ans=max(ans,dfs(dfs,i));}cout<<ans<<endl;}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}

cf1624G

题意

定义最小生成树的权值为所有边权的或运算，求最小生成树

思路

我们从高位开始贪心，考虑每一位是否可以为0，如果只使用这一位为0的边仍能得到生成树，那么说明这一位可以为0，就删去所有这一位不为0的边，如果不能得到生成树就说明这位只能为1，不删除任何边
由于边权最大值为1e9，我们最多跑30次kruscal即可

代码

#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"<<endl
#define i128 __int128using 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;
struct edge{ll u,v,w;bool operator <(const edge&t)const{return w<t.w;}
};int p[N];int find(int x)
{if(x!=p[x]) p[x]=find(p[x]);return p[x];
}bool merge(int x,int y)
{x=find(x);y=find(y);if(x==y) return false;p[x]=y;return true;
}void solve()
{int n,m;cin>>n>>m;vector<edge>e(m+1);for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;sort(all(e));vector<int>del(m+1);auto krus=[&](int x)->bool{for(int i=1;i<=n;i++) p[i]=i;int cnt=0;for(int i=1;i<=m;i++){if(del[i]) continue;if(e[i].w&(1ll<<x)) continue;int u=e[i].u;int v=e[i].v;if(merge(u,v)) cnt++;if(cnt==n-1) return true;}return false;};ll ans=0;for(int k=30;k>=0;k--){if(krus(k))//第k为可以为0就删除所有第k位为1的边{for(int i=1;i<=m;i++){ll w=e[i].w;if(w&(1ll<<k)) del[i]=1;}}else ans|=(1<<k);}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();return 0;
}

cf 2020D

题意

给定n个点和m次操作，每次操作给出a,d,k将连接 $a, a + d, a + 2 * d, a + 3 * d ... a + k * d$ 内的所有点， $\leq d \leq 10$

思路

暴力的做法是用并查集连接每次操作中的所有点，考虑优化，不难发现对于每次操作，所有 $[a, a + k * d]$ 内与 $\% d$ 同余的点都在一个连通块内，那么对于多次操作无疑会重复连接很多点，我们考虑按 $\% d$ 将所有操作的点区间分类，对于有交集的两个同类点区间他们一定在一个区间，那么可以对每个分类内的区间进行区间合并之后在对区间内的点连接

代码

#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"<<endl
#define i128 __int128using 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;int p[N];int find(int x)
{if(x!=p[x]) p[x]=find(p[x]);return p[x];
}void merge(int x,int y)
{x=find(x);y=find(y);if(x>y) swap(x,y);if(x!=y) p[x]=y;
}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++) p[i]=i;vector<PII>v[11][11];for(int i=1;i<=m;i++){int a,d,k;cin>>a>>d>>k;v[d][a%d].pb({a,a+k*d});}for(int i=1;i<=10;i++){for(int j=0;j<i;j++){sort(all0(v[i][j]));auto v1=v[i][j];for(int l=0,r=0;l<v1.size();l=r){int L=v1[l].fi;int R=v1[l].se;while(r<v1.size() && v1[r].fi<=R){R=max(R,v1[r].se);r++;}for(int p=L;p<R;p+=i) merge(p,p+i);}}}int cnt=0;for(int i=1;i<=n;i++) if(p[i]==i) cnt++;cout<<cnt<<endl;}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();return 0;
}

cf1388D

题意

给两个数组a和b，按顺序对每个i进行如下操作
1. $ans=ans+a_i$
2. $a_{b_i}=a_{b_i}+a_i(b_i!=-1)$
求可以得到最大的ans以及操作顺序
$−106≤ai≤106-10^6 \leq a_i \leq 10^6$

思路

对于 $a_i>0 且 b_i!=-1$ 的毫无疑问优先操作 $a_i$ 再操作 $a_{b_i}$ 更优，可以发现要求变成了对于某些点在某些点之前操作更优，不难想到拓扑排序，那么对于 $a_i<0$ 的点呢，无疑这些点放在最后操作，不影响其他点更优
那么我们可以对每个 $b_i!=-1$ 的点连一条 $a_i$ 到 $a_{b_i}$ 的边，拓扑排序的过程中，将 $a_i>0$ 的点正常计入路径答案中，而 $a_i<0$ 的点加入一个栈中，在答案的末尾输出即可

思路

#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"<<endl
#define i128 __int128using 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<ll>a(n+1),b(n+1);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];vector<int>d(n+1);for(int i=1;i<=n;i++){if(b[i]==-1) continue;e[i].pb(b[i]);d[b[i]]++;}queue<int>q;for(int i=1;i<=n;i++) if(!d[i]) q.push(i);stack<int>s;vector<int>path;ll ans=0;while(!q.empty()){auto t=q.front();q.pop();ans+=a[t];if(a[t]>0) path.pb(t);else s.push(t);for(auto ed:e[t]){if(a[t]>0) a[ed]+=a[t];d[ed]--;if(!d[ed]) q.push(ed);}}cout<<ans<<endl;for(auto t:path) cout<<t<<" ";while(!s.empty()) {cout<<s.top()<<" ";s.pop();}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;
}