2024.04.09 图论复习
P3403 跳楼机
同余最短路模板题。
设 \(d_i\) 表示只使用向上移动 \(y\) 层或 \(z\) 层两种功能，所能达到的最低楼层 \(p\)，其中 \(p\ mod\ x=i\) 。
两种连边方式：
- \(i\) 向 \((i+y)mod\ x\) 连权值为 \(y\) 的边；
- \(i\) 向 \((i+z)mod\ x\) 连权值为 \(z\) 的边；
则答案为：
\[\sum_{i=0}^{x-1}1+\lfloor\frac{h_i-d_i}{x}\rfloor \]#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
#define LL long long
const int maxn = 1e5 + 10;
int head[maxn],cnt=0;
struct edge{
int to,nxt;LL w;
}e[maxn<<1];
inline void link(int u,int v,LL w){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;e[cnt].w=w;
}
int x,y,z;
LL h,dis[maxn];
bool vis[maxn];
#define Pair pair<LL,int>
void dij(int s){
memset(dis,0x3f,sizeof dis);
priority_queue<Pair,vector<Pair>,greater<Pair> > q;
dis[s%x]=1;q.push(make_pair(0,s));
while(q.size()){
int u=q.top().second;q.pop();
if(vis[u])continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
int main(){
h=read<LL>();
x=read();y=read();z=read();
for(int i=0;i<x;i++){
link(i,(i+y)%x,y);
link(i,(i+z)%x,z);
}
dij(1);
LL ans=0;
for(int i=0;i<x;i++){
if(dis[i]<=h)ans+=1+(h-dis[i])/x;
}
cout<<ans<<endl;
return 0;
}
P3225 [HNOI2012] 矿场搭建
求出割点再从点双内部的点（非割点）出发，即可遍历到该 \(scc\) 的所有点，以统计大小等信息。
- 如果该点双内无割点，则需要建两个出口。
- 如果该点双内有且仅有一个割点，说明是缩点后的叶子节点，需要在除割点之外的位置建一个出口。
- 如果该点双内有两个及以上个割点，则不需要建出口。
#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
#define LL long long
const int maxn = 1e3 + 5;
int head[maxn],cnt;
struct edge{
int to,nxt;
}e[maxn<<1];
inline void link(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int dfn[maxn],low[maxn],idx;
bool cut[maxn];
int tag[maxn],tim;
int rt,sz,num;
void tarjan(int u,int fa){
dfn[u]=low[u]=++idx;
int pson=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
if(!dfn[v]){
pson++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u] && u!=rt)cut[u]=true;
}
else low[u]=min(low[u],dfn[v]);
}
if(u==rt && pson>=2)cut[u]=true;
}
int n,m,kase;
inline void clear(){
cnt=idx=rt=tim=sz=0;
memset(head,0,sizeof head);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(tag,0,sizeof tag);
memset(cut,false,sizeof cut);
}
void dfs(int u,int fa){
tag[u]=tim;
if(cut[u])return ;
sz++;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
if(cut[v] && tag[v]!=tim)tag[v]=tim,num++;
if(!tag[v])dfs(v,u);
}
}
int main(){
while(1){
m=read();if(!m)break;
clear();
n=0;
for(int i=1;i<=m;i++){
int u=read(),v=read();
link(u,v);link(v,u);
n=max(n,max(u,v));
}
for(int i=1;i<=n;i++)if(!dfn[i]){
rt=i;tarjan(i,0);
}
LL ans1=0,ans2=1;
for(int i=1;i<=n;i++){
if(tag[i] || cut[i])continue;
sz=num=0;tim++;
dfs(i,0);
if(!num)ans1+=2,ans2*=1LL*sz*(sz-1)/2;
else if(num==1)ans1++,ans2*=1LL*sz;
}
printf("Case %d: %lld %lld\n",++kase,ans1,ans2);
}
return 0;
}
CF909E Coprocessor
拓扑排序，但是不好直接在图上根据任务的执行情况（主处理器或副处理器）进行 \(dp\)。
可以每轮先把能进行的主处理器任务进行了，再进行副处理器任务直至再无可一起处理的副处理器任务，每轮操作的贡献即为 \(1\)。
#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
#define LL long long
const int maxn = 1e5 + 10;
int head[maxn],cnt;
struct edge{
int to,nxt;
}e[maxn];
inline void link(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int n,m,op[maxn],deg[maxn];
int topo(){
queue<int> q[2];
for(int i=1;i<=n;i++){
if(!deg[i])q[op[i]].push(i);
}
int ans=0;
while(q[0].size() || q[1].size()){
while(q[0].size()){
int u=q[0].front();q[0].pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(--deg[v]==0)q[op[v]].push(v);
}
}
if(q[1].size())ans++;
while(q[1].size()){
int u=q[1].front();q[1].pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(--deg[v]==0)q[op[v]].push(v);
}
}
}
return ans;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)op[i]=read();
for(int i=1;i<=m;i++){
int u=read()+1,v=read()+1;
link(v,u);deg[u]++;
}
printf("%d\n",topo());
return 0;
}