首页 > 其他分享 >2024.4.9 图论补题

2024.4.9 图论补题

时间:2024-04-09 22:24:49浏览次数:20  
标签:图论 ch 2024.4 int ++ maxn 补题 && include

P3225 [HNOI2012] 矿场搭建

如果没有割点,至少需要建立两个出口

如果只有一个割点,只需要设立一个出口

如果有两个及以上个割点,则无需建立,可以直接到达其他联通块

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define maxn 1010
#define INF 0x3f3f3f3f

using namespace std;

int n,tot,Tot,t,cnt,res,js,top,Cnt,Num;
int fr[maxn],to[maxn],Head[maxn],num[maxn],siz[maxn];
int ge[maxn],no[maxn];
bool vis[maxn],flag[maxn],pd[maxn];
int low[maxn],head[maxn],dfn[maxn];
int Dfn[maxn],Low[maxn],Vis[maxn],Zhan[maxn];
struct edge{int fr,to,nxt;}e[maxn<<1];

int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*w;
}

void add(int fr,int to){
	e[++tot].to=to;e[tot].fr=fr;
	e[tot].nxt=head[fr];head[fr]=tot;
}

void clear(){
	tot=js=cnt=t=res=Tot=0;
    memset(pd,0,sizeof pd);
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(no,0,sizeof no);
	memset(ge,0,sizeof ge);
	memset(vis,0,sizeof vis);
	memset(head,0,sizeof head);
	memset(flag,0,sizeof flag);
    memset(Vis,0,sizeof Vis);
    memset(siz,0,sizeof siz);
}

void tarjan1(int u,int fat){
	dfn[u]=low[u]=++cnt;
	vis[u]=1;int chi=0;
	for(int i=head[u];i;i=e[i].nxt){
		int To=e[i].to;
		if(!vis[To]){
			chi++;tarjan1(To,u);
			low[u]=min(low[u],low[To]);
			if(fat!=u&&low[To]>=dfn[u]&&!flag[u]){
				flag[u]=1;res++;
			}
		}
		else if(To!=fat) low[u]=min(low[u],dfn[To]);
	}
	if(fat==u&&chi>=2&&!flag[u]){
		flag[u]=1;res++;
	}
}

void tarjan2(int u){
	Zhan[++top]=u;Vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(!Vis[to]){
			tarjan2(to);
			if(low[to]>=dfn[u]){
				++t;int pre=Zhan[top];
				while(pre!=u){
					--top;
					if(flag[pre]) ++ge[t];
					else ++no[t];
					pre=Zhan[top];
				}
				if(flag[pre]) ++ge[t];
				else ++no[t];
			}
		}
	}
}

int main(){
	while(cin>>n&&n){
		clear();
		for(int i=1;i<=n;i++){
			fr[i]=read();to[i]=read();
			add(fr[i],to[i]);add(to[i],fr[i]);
			if(!pd[fr[i]]) pd[fr[i]]=1,js++;
			if(!pd[to[i]]) pd[to[i]]=1,js++;
		}
		
		for(int i=1;i<=js;i++) if(!vis[i]){cnt=0;tarjan1(i,i);}
		
        for(int i=1;i<=js;i++) if(!Vis[i]) tarjan2(i);
		long long ans=1;int get=0;
		
		
		for(int i=1;i<=t;i++){
			if(ge[i]>=2) continue;
			else if(ge[i]==1){++get;ans*=no[i];}
			else if(ge[i]==0){get+=2;ans*=(no[i]*(no[i]-1)/2);}
		}
		printf("Case %d: %d %lld\n",++Num,get,ans);
	}
	return 0;
}

CF909E Coprocessor

拓扑排序,让入度为零的点进队,做完主处理器判断副处理器的队列中有无点即可。

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100010
#define INF 0x3f3f3f3f
//#define int long long

using namespace std;

bool vis[maxn];
int n,m,tot,ans;
int head[maxn],du[maxn];
struct edge{int fr,to,nxt;}e[maxn];

int read(){
  int s=0,w=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
  return s*w;
}

void add(int fr,int to){
  e[++tot]=(edge){fr,to,head[fr]};head[fr]=tot;
}

void Topsort(){
  queue<int> q1,q2;
  for(int i=1;i<=n;i++) 
    if(!du[i]){
      if(!vis[i]) q1.push(i);
      else q2.push(i);
    }
  while(!q1.empty()||!q2.empty()){
    while(!q1.empty()){
      int u=q1.front();q1.pop();
      for(int i=head[u];i;i=e[i].nxt){
        int to=e[i].to;du[to]--;
        if(!du[to]){
          if(!vis[to]) q1.push(to);
          else q2.push(to);
        }
      }
    }
    ans+=(!q2.empty());
    while(!q2.empty()){
      int u=q2.front();q2.pop();
      for(int i=head[u];i;i=e[i].nxt){
        int to=e[i].to;du[to]--;
        if(!du[to]){
          if(!vis[to]) q1.push(to);
          else q2.push(to);
        }
      }
    }
  }
}

int main(){
  n=read();m=read();
  for(int i=1;i<=n;i++) vis[i]=read();
  for(int i=1,fr,to;i<=m;i++){
    fr=read()+1;to=read()+1;
    add(fr,to);du[to]++;
  }
  Topsort();
  printf("%d\n",ans);
  return 0;
}

P3403 跳楼机

同余最短路模板

\(f_i\) 为通过 2 3 操作到达 \(\text mod x=i\) 楼层的最小楼层

从 \(i\) 向 \(i+y,i+z\) 建立权值为 \(y,z\) 的边。

然后剩下楼层由操作一完成,贡献为 \((h-f_i)/x +1\)

#include<bits/stdc++.h>
#define maxn 200100
#define INF 0x3f3f3f3f
#define int long long

using namespace std;

bool vis[maxn];
int h,x,y,z,tot,ans;
int Dis[maxn],head[maxn];
struct edge{int fr,to,dis,nxt;}e[maxn<<2];

int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
	return s*w;
}

void add(int fr,int to,int dis){
	e[++tot]=(edge){fr,to,dis,head[fr]};head[fr]=tot;
}

void SPFA(){
	memset(Dis,INF,sizeof Dis);
	memset(vis,false,sizeof vis);
	deque<int> q;q.push_back(1);
	Dis[1]=1;vis[1]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop_front();vis[u]=false;
		for(int i=head[u];i;i=e[i].nxt){
			int to=e[i].to;
			if(Dis[to]>Dis[u]+e[i].dis){
				Dis[to]=Dis[u]+e[i].dis;
				if(!vis[to]){
					vis[to]=1;
					if(!q.empty()&&Dis[q.front()]>Dis[to])q.push_front(to);
					else q.push_back(to);
				}
			}
		}
	}
}

signed main(){
	h=read();
	x=read();y=read();z=read();
	if(x==1||y==1||z==1){cout<<h;return 0;}
	for(int i=0;i<x;i++)
		add(i,(i+y)%x,y),add(i,(i+z)%x,z);
	SPFA();
	for(int i=0;i<x;i++)
		if(Dis[i]<=h) ans+=(h-Dis[i])/x+1;
	printf("%lld\n",ans);
	return 0;
}

标签:图论,ch,2024.4,int,++,maxn,补题,&&,include
From: https://www.cnblogs.com/KnightL/p/18124985

相关文章

  • 2024.04.09 图论复习
    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\)的......
  • 2024.4.9 avx加速一维卷积操作(汇总)
    第三次作业提交内容一:源代码在-O3编译优化下执行结果:AVX指令集优化://conv_avx.cppboolConvolve1D_Ks5_F64_AVX(double*__restrict__y,constdouble*__restrict__x,constdouble*__restrict__kernel,int64_tnum_pts){constexprint64_tkernel_size=5......
  • 图论学习笔记
    Dijkstra单源最短路径堆优化。注意要定义成小根堆,而priority_queue默认大根堆再就是每个点最多入队一次,可以用vis数组记录证明:如果已经出队,说明队列中全都是val值比他大的(负权边?),这样他的val值一定已经是最终值了;如果没有入队,进行更改之后会在堆中体现,不需要担心之后还会更......
  • 2024.4.9 AVX加速卷积part2
    AVX加速卷积part2重新构筑下昨天的想法:问题:源程序在O2下的执行时间:经过AVX改进后的执行时间:下面尝试在AVX2基础上改进:AVX与AVX2的主要区别和改进:向量整数指令:AVX主要集中在浮点数运算上,提供了对256位宽SIMD(单指令多数据)向量的支持。AVX2引入了向量整数运算的支持。这......
  • 2024.4.8 数据结构课件补题
    [AGC055B]ABCSupremacy令ABC分别为1,2,3,然后令\(s_i=(s_i-i)\textmod3\)且结果大于0。然后可以发现三种组合均为连贯的三个相同数。且可以自由移动。可以选择每遇到三个相同数就删掉,或者不断加入栈,如果栈顶三个数相同全部弹出。再比较剩下的数即可。#include<bits......
  • 2024/4/8 课件补题
    2024/4/8课件补题[AGC055B]ABCSupremacy思维题。发现所有的\(ABC\),\(BCA\),\(CAB\)都可以任意向左向右移动,所以只需要把所有的\(ABC\)挪到字符串结尾即可,具体操作时可以删掉再比对\(s\)和\(t\)是否相同。#include<bits/stdc++.h>usingnamespacestd;#defineld......
  • 云原生周刊:2024 年 K8s 基准报告 | 2024.4.8
    开源项目推荐ArgoCDImageUpdaterArgoCDImageUpdater是一个自动更新ArgoCD管理的Kubernetes工作负载容器镜像的工具。简而言之,它将跟踪ArgoCD应用程序资源上的注释指定的图像版本,并通过使用ArgoCDAPI设置参数覆盖来更新它们。目前,它仅适用于使用Kustomize......
  • 2024.4.8 pytorch框架初上手
    pytorchPyTorch是一个针对深度学习,并且使用GPU和CPU来优化的tensorlibrary(tensor库)中文文档:https://pytorch.org/resources梯度/导数计算#linear.pyimporttorchimportnumpyasnpx=torch.tensor(3,)w=torch.tensor(4.,requires_grad=True)b=t......
  • 2024.4.7 训练1(rating) Codeforces Global Round 25
    https://codeforces.com/contest/1951题解参考:https://zhuanlan.zhihu.com/p/691034931A题一开始的思路比较绕,wa很多发卡了半小时才过。hansun的思路比较硬直,他在极短的时间内过了Ahansun的题解:https://codeforces.com/contest/1951/submission/255262403我的想法是分奇偶情......
  • [护网必备]知攻善防实验室蓝队应急响应工具箱v2024.4
    前言蓝队工具箱是为打造一款专业级应急响应的集成多种工具的工具集,由真实应急响应环境所用到的工具进行总结打包而来,由ChinaRan404,W啥都学,清辉等开发者编写.把项目现场中所用到的工具连同环境一同打包,并实现“可移植性”“兼容性”“使用便捷”等优点。集成模块:“常用工具......