ZR 集训 Day26 - 图论进阶 · ooliver

一些笔记差分约束 2-SAT 三元环枚举最小树形图定义：有向图的最小生成树。算法：朴素算法：朱刘算法（见下面的例题）最优算法：Tarjan 优化朱刘算法（待学习） P1948 [USACO08JAN] Telephone Lines S 考虑二分答案 x，将边权大于 x 的边权设为 1，其余设成 0，跑一遍 01-BFS，如果长度小于或等于 k 即满足条件。代码： C++ #include using namespace std; const int N=1e3+5; int n,m,k; int dis[N],vis[N]; vector,int>> e; vector> g[N]; bool check(int x){ for(int i=1;ix)}); g[v].push_back({u,(w>x)}); } deque q; q.push_front(1); dis[1]=0; while(q.size()){ int u=q.front(); q.pop_front(); if(vis[u]) continue; vis[u]=1; for(auto[v,w]:g[u]){ if(w+dis[u]>n>>m>>k; for(int i=1,u,v,w;i>u>>v>>w; e.push_back({{u,v},w}); } int l=0,r=1e6+5; while(l>1; if(check(mid)) r=mid; else l=mid+1; } if(l==1e6+5) cout `#include using namespace std; const int N=1e3+5; int n,m,k; int dis[N],vis[N]; vectorpairpairint,int>,int>> e; vectorpairint,int>> g[N]; bool check(int x){ for(int i=1;in;i++) g[i].clear(),dis[i]=1e9,vis[i]=0; for(auto[node,w]:e){ auto[u,v]=node; g[u].push_back({v,(w>x)}); g[v].push_back({u,(w>x)}); } dequeint> q; q.push_front(1); dis[1]=0; while(q.size()){ int u=q.front(); q.pop_front(); if(vis[u]) continue; vis[u]=1; for(auto[v,w]:g[u]){ if(w+dis[u]dis[v]){ dis[v]=w+dis[u]; if(w) q.push_back(v); else q.push_front(v); } } } if(dis[n]k) return 1; return 0; } signed main(){ cin>>n>>m>>k; for(int i=1,u,v,w;im;i++){ cin>>u>>v>>w; e.push_back({{u,v},w}); } int l=0,r=1e6+5; while(lr){ int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } if(l==1e6+5) cout1; else coutl; return 0; }` AT_agc056_c [AGC056C] 01 Balanced 差分约束题。朴素的想法是设 sum_i 表示 0 的数量的前缀和，那就有以下约束： \begin{aligned} sum_r-sum_l &= \frac{(r-l+1)}{2} \\ sum_i &\ge sum_{i-1} \\ sum_i &\le sum_{i-1}+1 \\ \end{aligned} 但是如果根据这个关系建边，就会出现负边权，跑 SPFA 可能会被卡，所以考虑转化建边方法。因为等式的约束是一定存在的，为了没有负边权，我们考虑将等式右边变成 0。那我们可以考虑重新定义数组 sum： sum_i=sum_{i-1}+\begin{cases} 1 &\text{if} s[i]='0' \\ -1 &\text{if} s[i]='1' \\ \end{cases} 这样一来就得到了新的约束： \begin{aligned} sum_l &= sum_r \\ sum_i &\le sum_{i-1} +1 \\ sum_{i-1} + 1 &\le sum_{i}+1 \\ \end{aligned} 由于 sum 表示的是 0 的数量减 1 的数量，所以跑差分约束、最大化 sum 就能得到字典序最小的解。代码： C++ #include using namespace std; const int N=1e6+5; int n,m; int dis[N],vis[N]; vector> g[N]; void dij(){ priority_queue> q; memset(dis,0x3f,sizeof dis); q.push({0,0}); dis[0]=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; for(int i=1;i>l>>r; g[l-1].push_back({r,0}); g[r].push_back({l-1,0}); } for(int i=1;i `#include using namespace std; const int N=1e6+5; int n,m; int dis[N],vis[N]; vectorpairint,int>> g[N]; void dij(){ priority_queuepairint,int>> q; memset(dis,0x3f,sizeof dis); q.push({0,0}); dis[0]=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}); } } } } signed main(){ cin>>n>>m; for(int i=1;im;i++){ int l,r; cin>>l>>r; g[l-1].push_back({r,0}); g[r].push_back({l-1,0}); } for(int i=1;in;i++){ g[i].push_back({i-1,1}); g[i-1].push_back({i,1}); } dij(); for(int i=1;in;i++) cout(dis[i]dis[i-1]); return 0; }` P1989 【模板】无向图三元环计数三元环计数模板，上面有步骤与复杂度分析。代码： C++ #include using namespace std; const int N=1e5+5; int n,m,ans; int deg[N],tag[N]; vector> e; vector g[N]; signed main(){ cin>>n>>m; for(int i=1;i>u>>v; e.push_back({u,v}); deg[u]++,deg[v]++; } for(auto[u,v]:e){ if(deg[u]>deg[v]||(deg[u]==deg[v]&&u>v)) swap(u,v); g[u].push_back(v); } for(int u=1;u `#include using namespace std; const int N=1e5+5; int n,m,ans; int deg[N],tag[N]; vectorpairint,int>> e; vectorint> g[N]; signed main(){ cin>>n>>m; for(int i=1;im;i++){ int u,v; cin>>u>>v; e.push_back({u,v}); deg[u]++,deg[v]++; } for(auto[u,v]:e){ if(deg[u]>deg[v]||(deg[u]==deg[v]&&u>v)) swap(u,v); g[u].push_back(v); } for(int u=1;un;u++){ for(int v:g[u]) tag[v]=1; for(int v:g[u]) for(int w:g[v]) if(tag[w]) ans++; for(int v:g[u]) tag[v]=0; } coutans; return 0; }` CF229C Triangles 乍一看是三元环计数，但是和三元环计数没什么关系。考虑将选出的边和未被选出的边染成两种颜色，那答案就是求完全图中颜色相同的三元环的数量，容斥一下就是 C_n^3 减去颜色不同的三角形的数量。考虑计算颜色相同的角的个数，应该等于颜色相同的三元环的数量乘三加上颜色不同的三角形的数量，设其为 cnt，有： \begin{aligned} ans&=C_n^3-(cnt-3\times ans) \\ &=\frac{cnt-C_n^3}{2} \end{aligned} 代码： C++ #include using namespace std; #define int long long const int N=1e6+5; int n,m,cnt; int deg[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1,u,v;i>u>>v; deg[u]++,deg[v]++; } for(int i=1;i `#include using namespace std; #define int long long const int N=1e6+5; int n,m,cnt; int deg[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1,u,v;im;i++){ cin>>u>>v; deg[u]++,deg[v]++; } for(int i=1;in;i++){ int c1=deg[i],c2=n-1-deg[i]; cnt+=c1*(c1-1)/2+c2*(c2-1)/2; } cout(cnt-n*(n-1)*(n-2)/6)/2; return 0; }` P3547 [POI 2013] CEN-Price List 考虑答案的三种可能：只走 a 都走只走 b 对于前两种可能性，我们直接跑 BFS 即可。对于第三种情况，我们考虑找到所有 u \rightarrow v \rightarrow w，且 u，w 之间没有边，然后使 u 花费 b 的代价跳到 w。这样正确性显然，但是复杂度会爆炸。根据 BFS 的性质，我们知道，w 第一次作为终点必然得到的就是最小的长度，所以我们把 u \rightarrow v \rightarrow w 这条路径中的两条边分为两类，一类是起点边，一类是终点边。具体地，我们先枚举起点边，再枚举终点边，如果答案得到更新，就把终点边从边集中删去。不难发现，一个三元环会被遍历三遍，其余的一边就被删掉了，所以复杂度可以看成 O(m\sqrt(m))。代码： C++ #include using namespace std; const int N=1e5+5; int n,m,k,a,b; int dis1[N],dis2[N],tag[N]; vector g[N],t[N]; void bfs1(int s){ memset(dis1,0x3f,sizeof dis1); queue q; q.push(s); dis1[s]=0; while(q.size()){ int u=q.front(); q.pop(); for(int v:g[u]){ if(dis1[u]+1 q; q.push(s); dis2[s]=0; while(q.size()){ int u=q.front(); q.pop(); for(int v:g[u]) tag[v]=1; for(int v:g[u]){ for(int i=0;i>n>>m>>k>>a>>b; for(int i=1,u,v;i>u>>v; g[u].push_back(v); g[v].push_back(u); t[u].push_back(v); t[v].push_back(u); } bfs1(k); bfs2(k); for(int i=1;i `#include using namespace std; const int N=1e5+5; int n,m,k,a,b; int dis1[N],dis2[N],tag[N]; vectorint> g[N],t[N]; void bfs1(int s){ memset(dis1,0x3f,sizeof dis1); queueint> q; q.push(s); dis1[s]=0; while(q.size()){ int u=q.front(); q.pop(); for(int v:g[u]){ if(dis1[u]+1dis1[v]){ dis1[v]=dis1[u]+1; q.push(v); } } } } void bfs2(int s){ memset(dis2,0x3f,sizeof dis2); queueint> q; q.push(s); dis2[s]=0; while(q.size()){ int u=q.front(); q.pop(); for(int v:g[u]) tag[v]=1; for(int v:g[u]){ for(int i=0;it[v].size();i++){ int w=t[v][i]; if(tag[w]) continue; if(dis2[u]+bdis2[w]){ dis2[w]=dis2[u]+b; q.push(w); swap(t[v][i],t[v][t[v].size()-1]); t[v].pop_back(); i--; } } } for(int v:g[u]) tag[v]=0; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m>>k>>a>>b; for(int i=1,u,v;im;i++){ cin>>u>>v; g[u].push_back(v); g[v].push_back(u); t[u].push_back(v); t[v].push_back(u); } bfs1(k); bfs2(k); for(int i=1;in;i++){ int ans=2e9; ans=min(ans,dis1[i]*a); ans=min(ans,(dis1[i]/2)*b+(dis1[i]&1)*a); ans=min(ans,dis2[i]); coutans"\n"; } return 0; }` P5100 [JOI 2017 Final] 足球 / Soccer 不难发现，球移动时有三种状态：带球移动被横向踢走被纵向踢走考虑对三种状态建分层图，因为踢球时需要额外的代价 B，我们可以看作其是连接“带球移动层”和“被踢走”的层的边的边权。对于从“被踢走”层回到“带球移动层”，我们需要找到离当前点最近的人，这个 BFS 预处理一下即可。代码： C++ #include using namespace std; #define id(x,y) ((x)*(w+1)+(y)) #define add(x,y,z) g[(x)].push_back({(y),(z)}) #define int long long const int N=1e6+5; const int M=505; int n,h,w,a,b,c; int dis1[M][M],dis[N],tag[M][M],vis[N],dx[]={0,0,1,-1},dy[]={1,-1,0,0}; vector> d,g[N]; void bfs(){ queue> q; for(auto[x,y]:d) dis1[x][y]=0,q.push({x,y}); while(q.size()){ auto[x,y]=q.front(); q.pop(); for(int i=0;ih||nyw) continue; if(!dis1[nx][ny]&&!tag[nx][ny]){ dis1[nx][ny]=dis1[x][y]+1; q.push({nx,ny}); } } } } void dij(){ memset(dis,0x3f,sizeof dis); priority_queue> q; q.push({0,id(d[0].first,d[0].second)}); dis[id(d[0].first,d[0].second)]=0; while(q.size()){ auto[ddd,u]=q.top(); q.pop(); if(vis[u]) continue; vis[u]=1; for(auto[v,wis]:g[u]){ if(!vis[v]&&dis[u]+wis>h>>w>>a>>b>>c>>n; for(int i=1,x,y;i>x>>y; tag[x][y]=1; d.push_back({x,y}); } bfs(); for(int x=0;xh||nyw) continue; add(id(x,y),id(nx,ny),c); if(i `#include using namespace std; #define id(x,y) ((x)*(w+1)+(y)) #define add(x,y,z) g[(x)].push_back({(y),(z)}) #define int long long const int N=1e6+5; const int M=505; int n,h,w,a,b,c; int dis1[M][M],dis[N],tag[M][M],vis[N],dx[…