ZR 集训 Day25 - 基础图论 · ooliver

前言昨天通知今天有台风，所以今天上午改成了神秘模拟赛，题目啥的放最后吧。 P5304 [GXOI/GZOI2019] 旅行者考虑二进制分组，即枚举 k 个关键点的编号的二进制位，将 0、1 分成两个集合，用一个超级源点连向一个集合、用一个超级汇点连向另一个集合，跑最短路即可。由于最终的答案的点对一定有一位上是不一样的，所以这个做法正确性显然。代码： C++ #include using namespace std; #define int long long #define pii pair const int N=1e5+5; struct graph{ int n; vector g[N]; void init(int x){ n=x; for(int i=1;i dis(n+1,1e18),vis(n+1,0); priority_queue q; q.push({0,s}); dis[s]=0; while(q.size()){ auto[d,u]=q.top(); q.pop(); if(vis[u]) continue; vis[u]=1; for(auto[v,w]:g[u]){ if(!vis[v]&&dis[u]+w>n>>m>>k; vector d(k+1),u(m+1),v(m+1),w(m+1); for(int i=1;i>u[i]>>v[i]>>w[i]; for(int i=1;i>d[i]; for(int j=0;j>j)&1) g.add(n+1,d[i],0); else g.add(d[i],n+2,0); } ans=min(ans,g.dij(n+1,n+2)); g.init(n+2); for(int i=1;i>j)&1) g.add(d[i],n+1,0); else g.add(n+2,d[i],0); } ans=min(ans,g.dij(n+2,n+1)); } cout>T; while(T--) solve(); return 0; } `#include using namespace std; #define int long long #define pii pair const int N=1e5+5; struct graph{ int n; vectorpii> g[N]; void init(int x){ n=x; for(int i=1;in;i++) g[i].clear(); } void add(int u,int v,int w){ g[u].push_back({v,w}); } int dij(int s,int t){ vectorint> dis(n+1,1e18),vis(n+1,0); priority_queuepii> q; q.push({0,s}); dis[s]=0; while(q.size()){ auto[d,u]=q.top(); q.pop(); if(vis[u]) continue; vis[u]=1; for(auto[v,w]:g[u]){ if(!vis[v]&&dis[u]+wdis[v]){ dis[v]=dis[u]+w; q.push({-dis[v],v}); } } } return dis[t]; } }g; void solve(){ int n,m,k,ans=1e18; cin>>n>>m>>k; vectorint> d(k+1),u(m+1),v(m+1),w(m+1); for(int i=1;im;i++) cin>>u[i]>>v[i]>>w[i]; for(int i=1;ik;i++) cin>>d[i]; for(int j=0;j19;j++){ g.init(n+2); for(int i=1;im;i++) g.add(u[i],v[i],w[i]); for(int i=1;ik;i++){ if((d[i]>>j)&1) g.add(n+1,d[i],0); else g.add(d[i],n+2,0); } ans=min(ans,g.dij(n+1,n+2)); g.init(n+2); for(int i=1;im;i++) g.add(u[i],v[i],w[i]); for(int i=1;ik;i++){ if((d[i]>>j)&1) g.add(d[i],n+1,0); else g.add(n+2,d[i],0); } ans=min(ans,g.dij(n+2,n+1)); } coutans"\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int T; cin>>T; while(T--) solve(); return 0; }` P1262 [POI 1996 R3] 间谍网络对拥有证据这个关系建边，形成一个有向图。对于图中的环，取点权最小的即可，可以考虑缩点成有向无环图，这样入度为 0 的点即无法控制的点，需要收买。代码： C++ #include using namespace std; const int N=1e5+5; int n,m,p,idx,sum,ans; int xu[N],xv[N],wis[N],mn[N],in[N]; int dfn[N],low[N],tag[N],scc[N]; stack st; vector g[N]; void tj(int u){ low[u]=dfn[u]=++idx,tag[u]=1; st.push(u); for(int v:g[u]){ if(!dfn[v]){ tj(v); low[u]=min(low[u],low[v]); } else if(tag[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ sum++; while(st.size()){ int x=st.top(); st.pop(); scc[x]=sum,tag[x]=0,mn[sum]=min(mn[sum],wis[x]); if(x==u) break; } } } signed main(){ scanf("%d%d",&n,&p); fill(wis+1,wis+1+n,1e9); fill(mn+1,mn+1+n,1e9); for(int i=1,id,w;i `#include using namespace std; const int N=1e5+5; int n,m,p,idx,sum,ans; int xu[N],xv[N],wis[N],mn[N],in[N]; int dfn[N],low[N],tag[N],scc[N]; stackint> st; vectorint> g[N]; void tj(int u){ low[u]=dfn[u]=++idx,tag[u]=1; st.push(u); for(int v:g[u]){ if(!dfn[v]){ tj(v); low[u]=min(low[u],low[v]); } else if(tag[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ sum++; while(st.size()){ int x=st.top(); st.pop(); scc[x]=sum,tag[x]=0,mn[sum]=min(mn[sum],wis[x]); if(x==u) break; } } } signed main(){ scanf("%d%d",&n,&p); fill(wis+1,wis+1+n,1e9); fill(mn+1,mn+1+n,1e9); for(int i=1,id,w;ip;i++){ scanf("%d%d",&id,&w); wis[id]=w; } scanf("%d",&m); for(int i=1;im;i++){ scanf("%d%d",xu+i,xv+i); g[xu[i]].push_back(xv[i]); } for(int i=1;in;i++) if(!dfn[i]&&wis[i]!=1e9) tj(i); for(int i=1;in;i++) if(!dfn[i]&&wis[i]==1e9){ printf("NO\n%d\n",i); return 0; } for(int i=1;im;i++) if(scc[xu[i]]!=scc[xv[i]]) in[scc[xv[i]]]=1; for(int i=1;isum;i++) if(!in[i]) ans+=mn[i]; printf("YES\n%d\n",ans); return 0; }` P2272 [ZJOI2007] 最大半连通子图首先知道强连通分量是肯定属于半联通分量的，之后不难发现在有向无环图中半联通分量就等价于一条链，我们把缩点后的 siz 看成点权，原问题就变成了找有向无环图中的最长链，拓扑+DP 即可。这里有个小知识，就是缩点后的 scc 编号正好是拓扑序倒过来，所以我们不需要再单独做一遍拓扑排序了。代码： C++ #include using namespace std; #define int long long const int N=1e5+5; const int M=1e6+5; int n,m,mod,idx,sum,ans,c; int xu[M],xv[M],dis[N],dfn[N],low[N],tag[N],scc[N],siz[N],num[N]; stack st; vector g[N],t[N]; map,bool> mp; queue q; void tj(int u){ low[u]=dfn[u]=++idx,tag[u]=1; st.push(u); for(int v:g[u]){ if(!dfn[v]){ tj(v); low[u]=min(low[u],low[v]); } else if(tag[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ sum++; while(st.size()){ int x=st.top(); st.pop(); scc[x]=sum,tag[x]=0,siz[sum]++; if(x==u) break; } } } signed main(){ cin>>n>>m>>mod; for(int i=1;i>xu[i]>>xv[i]; g[xu[i]].push_back(xv[i]); } for(int i=1;i=1;u--) for(int v:t[u]){ if(dis[u]+siz[v]>dis[v]){ dis[v]=dis[u]+siz[v]; num[v]=num[u]; } else if(dis[u]+siz[v]==dis[v]) (num[v]+=num[u])%=mod; ans=max(ans,dis[v]); } for(int u=1;u `#include using namespace std; #define int long long const int N=1e5+5; const int M=1e6+5; int n,m,mod,idx,sum,ans,c; int xu[M],xv[M],dis[N],dfn[N],low[N],tag[N],scc[N],siz[N],num[N]; stackint> st; vectorint> g[N],t[N]; mappairint,int>,bool> mp; queueint> q; void tj(int u){ low[u]=dfn[u]=++idx,tag[u]=1; st.push(u); for(int v:g[u]){ if(!dfn[v]){ tj(v); low[u]=min(low[u],low[v]); } else if(tag[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ sum++; while(st.size()){ int x=st.top(); st.pop(); scc[x]=sum,tag[x]=0,siz[sum]++; if(x==u) break; } } } signed main(){ cin>>n>>m>>mod; for(int i=1;im;i++){ cin>>xu[i]>>xv[i]; g[xu[i]].push_back(xv[i]); } for(int i=1;in;i++) if(!dfn[i]) tj(i); for(int i=1;im;i++){ if(scc[xu[i]]==scc[xv[i]]||mp[{scc[xu[i]],scc[xv[i]]}]) continue; mp[{scc[xu[i]],scc[xv[i]]}]=1; t[scc[xu[i]]].push_back(scc[xv[i]]); } for(int i=1;isum;i++) dis[i]=siz[i],num[i]=1,ans=max(ans,dis[i]); for(int u=sum;u>=1;u--) for(int v:t[u]){ if(dis[u]+siz[v]>dis[v]){ dis[v]=dis[u]+siz[v]; num[v]=num[u]; } else if(dis[u]+siz[v]==dis[v]) (num[v]+=num[u])%=mod; ans=max(ans,dis[v]); } for(int u=1;usum;u++) if(dis[u]==ans) (c+=num[u])%=mod; coutansendlc; return 0; }` P3275 [SCOI2011] 糖果按关系建边，之后缩点。如果缩点后存在强连通分量内的边边权为 1，说明无解，输出 -1；否则按照拓扑序 DP 即可。代码： C++ #include using namespace std; #define int long long const int N=1e5+5; int n,k,idx,sum,ans; int xu[N],xv[N],xw[N],dis[N],in[N]; int dfn[N],low[N],tag[N],scc[N],siz[N]; stack st; vector> g[N],t[N],e0,e1; map,bool> m0,m1; queue q; void tj(int u){ low[u]=dfn[u]=++idx,tag[u]=1; st.push(u); for(auto [v,w]:g[u]){ if(!dfn[v]){ tj(v); low[u]=min(low[u],low[v]); } else if(tag[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ sum++; while(st.size()){ int x=st.top(); st.pop(); scc[x]=sum,tag[x]=0,siz[sum]++; if(x==u) break; } } } signed main(){ cin>>n>>k; for(int i=1;i>op>>u>>v; if(op==1){ g[u].push_back({v,0}),e0.push_back({u,v}); g[v].push_back({u,0}),e0.push_back({v,u}); } if(op==2) g[u].push_back({v,1}),e1.push_back({u,v}); if(op==3) g[v].push_back({u,0}),e0.push_back({v,u}); if(op==4) g[v].push_back({u,1}),e1.push_back({v,u}); if(op==5) g[u].push_back({v,0}),e0.push_back({u,v}); } for(int i=1;i=1;u--) for(auto[v,w]:t[u]) dis[v]=max(dis[v],dis[u]+w); for(int i=1;i `#include using namespace std; #define int long long const int N=1e5+5; int n,k,idx,sum,ans; int xu[N],xv[N],xw[N],dis[N],in[N]; int dfn[N],low[N],tag[N],scc[N],siz[N]; stackint> st; vectorpairint,int>> g[N],t[N],e0,e1; mappairint,int>,bool> m0,m1; queueint> q; void tj(int u){ low[u]=dfn[u]=++idx,tag[u]=1; st.push(u); for(auto [v,w]:g[u]){ if(!dfn[v]){ tj(v); low[u]=min(low[u],low[v]); } else if(tag[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ sum++; while(st.size()){ int x=st.top(); st.pop(); scc[x]=sum,tag[x]=0,siz[sum]++; if(x==u) break; } } } signed main(){ cin>>n>>k; for(int i=1;ik;i++){ int op,u,v; cin>>op>>u>>v; if(op==1){ g[u].push_back({v,0}),e0.push_back({u,v}); g[v].push_back({u,0}),e0.push_back({v,u}); } if(op==2) g[u].push_back({v,1}),e1.push_back({u,v}); if(op==3) g[v].push_back({u,0}),e0.push_back({v,u}); if(op==4) g[v].push_back({u,1}),e1.push_back({v,u}); if(op==5) g[u].push_back({v,0}),e0.push_back({u,v}); } for(int i=1;in;i++) if(!dfn[i]) tj(i); for(auto[u,v]:e1){ if(scc[u]==scc[v]){ cout1; r…