首页 > 其他分享 >提高组图论专题 2

提高组图论专题 2

时间：2024-10-24 21:58:49浏览次数：4  
标签：图论 专题 vis int 提高 yy read xx dis

提高组图论专题 2

T1 [NOIP2013 提高组] 华容道

首先，暴力 BFS 即可 AC，但要注意以下几点：

  • 队列必须手写；
  • 用 \(\text{vis}\) 数组剪枝。

然后我们来看正解。参考这位的 DFS 思路，发现将暴力 DFS 改成每次让起点移动，具体过程为空格移动到起点、起点移动到空格，且在这个过程中空格不能经过起点。所以预处理从 \(a\) 点到 \(b\) 点不经过 \(c\) 的距离，考虑到这样会超时，发现起点一定挨着起点将要移动的位置，所以对于每个点只需处理相邻 4 点。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
constexpr int MAXN=35;
constexpr int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,m,Q,a[MAXN][MAXN],ex,ey,sx,sy,tx,ty,ans;
int vis[MAXN][MAXN][MAXN][MAXN];
int dis[MAXN][MAXN][MAXN][MAXN][4];
bool ins[MAXN][MAXN];
struct Node{
	int sx,sy;
	bool operator<(const Node&x)const{
		return sx<x.sx;
	}
};
void dijkstra(int ex,int ey,int sx,int sy,int typ){
	memset(ins,0,sizeof(ins));
	priority_queue<pair<int,Node>>q;
	q.emplace(dis[ex][ey][ex][ey][typ]=0,(Node){ex,ey});
	while(!q.empty()){
		Node tp=q.top().second;
		q.pop();
		if(ins[tp.sx][tp.sy])continue;
		ins[tp.sx][tp.sy]=1;
		for(int i=0,xx,yy;i<4;++i){
			xx=tp.sx+dx[i],yy=tp.sy+dy[i];
			if(xx<1||xx>n||yy<1||yy>m||!a[xx][yy]||(xx==sx&&yy==sy))continue;
			if(dis[ex][ey][xx][yy][typ]>dis[ex][ey][tp.sx][tp.sy][typ]+1){
				dis[ex][ey][xx][yy][typ]=dis[ex][ey][tp.sx][tp.sy][typ]+1;
				q.emplace(-dis[ex][ey][xx][yy][typ],(Node){xx,yy});
			}
		}
	}
}
void dfs(int ex,int ey,int sx,int sy,int res){
	if(res>=ans)return;
	if(sx==tx&&sy==ty)return ans=min(ans,res),void();
	if(vis[ex][ey][sx][sy]<=res)return;
	vis[ex][ey][sx][sy]=res;
	for(int i=0,xx,yy;i<4;++i){
		xx=sx+dx[i],yy=sy+dy[i];
		if(xx<1||xx>n||yy<1||yy>m||!a[xx][yy])continue;
		dfs(sx,sy,xx,yy,res+dis[xx][yy][ex][ey][(i+2)%4]+1);
	}
}

int main(){
	n=read(),m=read(),Q=read();
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=read();
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			if(!a[i][j])continue;
			for(int k=0,xx,yy;k<4;++k){
				xx=i+dx[k],yy=j+dy[k];
				if(xx<1||xx>n||yy<1||yy>m||!a[xx][yy])continue;
				dijkstra(i,j,xx,yy,k);
			}
		}
	while(Q--){
		memset(vis,0x3f,sizeof(vis));
		ex=read(),ey=read(),sx=read(),sy=read(),tx=read(),ty=read(),ans=0x3f3f3f3f;
		dfs(ex,ey,sx,sy,0);
		write(ans==0x3f3f3f3f?-1:ans);
	}
	return fw,0;
}

题解说这样写有 85pts，但实际上我直接 AC 了，不知是不是我常数小的问题。

题水跟我有什么关系

T2 Star Way To Heaven

《路径上最小距离最大值》，很难不让人想到最小生成树。考虑到将所有 \(\text{Star}\) 按两两间最短距离排序后依次连线，则最终我们的小 W 的最优答案一定是这些线的长度中最长的那条的长度除以 2。

这个两两间最短距离就很灵性，我们考虑求出这个两两间最短距离。所以可以用 Prim 算法跑一遍，得到最短路径（即最小生成树），然后统计答案即可。

注意这里不能用队列来维护，因为这样统计到的答案会不全。发现 \(k\) 只有 \(6000\)，所以 \(O(k^2)\) 是不成问题的，就不要像我一样老想着队列了。

#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;

char buf[1<<20],*p1=buf,*p2=buf;
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
using pii=pair<int,int>;
using ld=long double;
constexpr int MAXN=6005;
int m,n,k,pre[MAXN];
struct{
	int x,y;
}a[MAXN];
ld dis[MAXN],ans;
bool vis[MAXN];

ld Dis(int x,int y){
	if(x>y)swap(x,y);
	if(!x||y==k+1)return abs(a[x].y-a[y].y)*0.5l;
	return hypot(a[x].x-a[y].x,a[x].y-a[y].y)*0.5l;
}
void prim(){
	for(int i=0;i<=k+1;++i)dis[i]=2e9;
	dis[0]=0;
	for(int i=0;i<=k+1;++i){
		int u=0;
		ld minn=2e9;
		for(int j=0;j<=k+1;++j)
			if(!vis[j]&&minn>dis[j])
				minn=dis[j],u=j;
		vis[u]=1;
		if(u==k+1)break;
		for(int j=0;j<=k+1;++j)
			if(!vis[j]&&j^u&&dis[j]>Dis(u,j)){
				dis[j]=Dis(u,j);
				pre[j]=u;
			}
	}
}
int main(){
	m=read(),n=read(),k=read();
	for(int i=1;i<=k;++i)a[i]={read(),read()};
	a[k+1].y=n;
	prim();
	int x=k+1;
	while(x)ans=max(ans,Dis(pre[x],x)),x=pre[x];
	printf("%.10Lf\n",ans);
	return 0;
}

T3 [CF1005F] Berland and the Shortest Paths

前置芝士：最短路径树。

知道这个这个题就很简单了，由于边权为 \(1\)，可以先跑 BFS 求出每个点所有能转移到它的边的集合，答案就是 \(\min\big(\prod\text{siz}_i,k\big)\)。题目要求输出可行解，于是跑个 DFS 输出就完了。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
constexpr int MAXN=2e5+5;
int n,m,k,head[MAXN],tot=1;
struct{int v,to;}e[MAXN<<1];
void addedge(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
vector<int>pre[MAXN];
int dis[MAXN],cnt,ans=1;
bool vis[MAXN];
void bfs(){
	memset(dis,0x3f,sizeof(int)*(n+5));
	dis[1]=0;
	queue<int,list<int>>q;
	q.emplace(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].to)
			if(dis[e[i].v]>dis[u]+1){
				dis[e[i].v]=dis[u]+1;
				pre[e[i].v].emplace_back(i);
				q.emplace(e[i].v);
			}else if(dis[e[i].v]==dis[u]+1)
				pre[e[i].v].emplace_back(i);
	}
}
void dfs(int u){
	if(u>n){
		for(int i=1;i<=m;++i)write(vis[i],'#');
		putchar('\n');
		if(++cnt==ans)fw,exit(0);
		return;
	}
	for(auto x:pre[u]){
		vis[x>>1]=1;
		dfs(u+1);
		vis[x>>1]=0;
	}
}

int main(){
	n=read(),m=read(),k=read();
	for(int i=1,u,v;i<=m;++i){
		u=read(),v=read();
		addedge(u,v),addedge(v,u);
	}
	bfs();
	for(int i=2;i<=n;++i)
		if(ans*(long long)pre[i].size()>k){
			ans=k;
			break;
		}else ans*=pre[i].size();
	write(ans);
	memset(vis,0,sizeof(int)*(m+5));
	dfs(2);
	return fw,0;
}

T4 [JOI 2017 Final] 足球 / サッカー (Soccer)

分层图好题。

对于这种题面很长、转移很复杂的题目，显然不能 DP，考虑转化为分层图最短路问题。对于每个点 \((i,j)\)，它需要设置五个状态：控球，以及向上/下/左/右踢球。为什么踢球要设置四个状态呢？因为球在被踢的过程中不能转向。

然后是本题的重点：连边。

  1. 当前运球点向周围运球点连双向边，边权为 \(C\)；
  2. 四个踢球点分别向相邻对应的点连单向边，边权为 \(A\)；
    注意判断是否越界。
  3. 对于当前位置的五个点，当前运球点向当前四个踢球点连单向边，边权为 \(B\)；
    注意这是很妙的一步，原本这个 \(B\) 的贡献是踢球踢出来的，现在将这个贡献提前到运球转踢球这个过程中。
  4. 对于当前位置的五个点，当前四个踢球点向当前运球点连单项边，边权为 \(\text{dis}\times C\)；
    解释一下，因为这种连边方式需要最近的球员跑过来，所以这个 \(\text{dis}\) 是当前点到最近球员的距离。BFS 可以很容易地求出。

连完了所有边之后跑 Dijkstra 就行。注意起始点是 \((S_1,T_1)\) 而不是 \((1,1)\)，结束点是 \((S_N,T_N)\) 而不是 \((H,W)\)。

思路还是很清晰的，三步走：BFS、连边、Dijkstra。

#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;

char buf[1<<20],*p1=buf,*p2=buf;
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
using ll=long long;
constexpr int MAXH=505,MAXN=1e5+5;
constexpr int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int h,w,a,b,c,n,S;
struct Node{
	int s,t;
	Node(int s=0,int t=0): s(s),t(t) {}
}s[MAXN];
int head[MAXH*MAXH*5],tot;
struct{int v,to;ll w;}e[MAXH*MAXH*50];
void addedge(int u,int v,ll w){
	e[++tot]={v,head[u],w};
	head[u]=tot;
}
ll dis[MAXH*MAXH*5];
bool vis[MAXH*MAXH*5];
queue<Node>q;
int R(int x,int y){
	return (x-1)*w+y;
}

void bfs(){
	while(!q.empty()){
		int x=q.front().s,y=q.front().t;
		q.pop();
		for(int i=0,xx,yy,r;i<4;++i){
			xx=x+dx[i],yy=y+dy[i];
			if(xx<1||xx>h||yy<1||yy>w||vis[r=R(xx,yy)]||dis[r]<=dis[R(x,y)]+c)continue;
			vis[r]=1;
			dis[r]=dis[R(x,y)]+c;
			q.emplace(xx,yy);
		}
	}
}

void add(){
	for(int x=1;x<=h;++x)
		for(int y=1;y<=w;++y){
			int r=R(x,y);
			addedge(r,r+S,b),addedge(r,r+S*2,b),addedge(r,r+S*3,b),addedge(r,r+S*4,b);
			addedge(r+S,r,dis[r]),addedge(r+S*2,r,dis[r]),addedge(r+S*3,r,dis[r]),addedge(r+S*4,r,dis[r]);
			// 0上1下2左3右
			for(int i=0,xx,yy;i<4;++i){
				xx=x+dx[i],yy=y+dy[i];
				if(xx<1||xx>h||yy<1||yy>w)continue;
				int t=R(xx,yy);
				addedge(r,t,c);
				switch(i){
					case 0: addedge(r+S,t+S,a);break;
					case 1: addedge(r+S*2,t+S*2,a);break;
					case 2: addedge(r+S*3,t+S*3,a);break;
					default: addedge(r+S*4,t+S*4,a);break;
				}
			}
		}
}

void dijkstra(){
	priority_queue<pair<ll,int>>q;
	memset(dis,0x3f,sizeof(ll)*(h*w*5+5));
	memset(vis,0,sizeof(bool)*(h*w*5+5));
	q.emplace(dis[R(s[1].s,s[1].t)]=0,R(s[1].s,s[1].t));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].to)
			if(dis[e[i].v]>dis[u]+e[i].w){
				dis[e[i].v]=dis[u]+e[i].w;
				q.emplace(-dis[e[i].v],e[i].v);
			}
	} 
}

int main(){
	h=read()+1,w=read()+1,a=read(),b=read(),c=read(),n=read();
	S=R(h,w);
	memset(dis,0x3f,sizeof(ll)*(h*w+5));
	for(int i=1,r;i<=n;++i){
		s[i]={read()+1,read()+1};
		r=R(s[i].s,s[i].t);
		dis[r]=0,vis[r]=1;
		q.emplace(s[i]);
	}
	bfs();
	add();
	dijkstra();
	const int F=R(s[n].s,s[n].t);
	printf("%lld\n",min({dis[F],dis[F+S],dis[F+S*2],dis[F+S*3],dis[F+S*4]}));
	return 0;
}

T5 [CF1981E] Turtle and Intersected Segments

发现瓶颈在于连边，考虑优化这个过程。发现对于三条两两相交的线段（设边权为 \(a_1,a_2,a_3\) 且 \(a_1\le a_2\le a_3\)），需要连的边只有两条：\((a_1,a_2)\) 和 \((a_2,a_3)\)。因为易得 \((a_1,a_3)\) 一定不会出现在最小生成树上。

所以我们考虑这样的一个扫描线流程：每条线段在 \(l\) 处加入、在 \(r\) 处删除，\(O(n)\) 地扫描，每加入一条线段时向它的前驱、后继连边。用 multiset 维护即可做到 \(O(n\log n)\)，而边数降到了 \(O(n)\)，然后跑 Kruskal 就完了。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
constexpr int MAXN=5e5+5;
int t,n;
struct{int l,r,a;}s[MAXN];
int b[MAXN<<1],tot,tt,fuc,cnt;
pair<int,int> c[MAXN<<1];
struct Edge{
	int u,v,w;
	bool operator<(const Edge&x)const{
		return w<x.w;
	}
}e[MAXN];
int f[MAXN];
int find(int x){
	if(f[x]^x)f[x]=find(f[x]);
	return f[x];
}
void kruskal(){
	iota(f+1,f+n+1,1);
	sort(e+1,e+fuc+1);
	long long ans=0;
	for(int i=1,fu,fv;i<=fuc;++i){
		fu=find(e[i].u),fv=find(e[i].v);
		if(fu==fv)continue;
		f[fv]=fu;
		ans+=e[i].w;
		if(++cnt==n-1)break;
	}
	write(cnt==n-1?ans:-1);
}

int main(){
	t=read();
	while(t--){
		tot=tt=fuc=cnt=0;
		n=read();
		for(int i=1;i<=n;++i){
			s[i]={read(),read(),read()};
			b[++tot]=s[i].l;
			b[++tot]=++s[i].r;
		}
		sort(b+1,b+tot+1);
		tot=unique(b+1,b+tot+1)-b-1;
		for(int i=1;i<=n;++i){
			s[i].l=lower_bound(b+1,b+tot+1,s[i].l)-b;
			s[i].r=lower_bound(b+1,b+tot+1,s[i].r)-b;
			c[++tt]=make_pair(s[i].l,i);
			c[++tt]=make_pair(s[i].r,-i);
		}
		sort(c+1,c+tt+1);
		multiset<pair<int,int>>st;
		for(int i=1,j;i<=tt;++i){
			j=c[i].second;
			if(j>0){
				auto it=st.emplace(s[j].a,j);
				if(it!=st.begin()){
					int k=prev(it)->second;
					e[++fuc]={j,k,abs(s[j].a-s[k].a)};
				}
				if(next(it)!=st.end()){
					int k=next(it)->second;
					e[++fuc]={j,k,abs(s[j].a-s[k].a)};
				}
			}else st.erase(make_pair(s[-j].a,-j));
		}
		kruskal();
	}

	return fw,0;
}

T6 [JOISC 2017 Day 2] 火车旅行

标签：图论,专题,vis,int,提高,yy,read,xx,dis
From： https://www.cnblogs.com/laoshan-plus/p/18501432

相关文章

  • 【MySQL】提高篇—理论讲解与案例分析：实践练习：编写复杂查询、创建视图和存储过程
    关系数据库是存储和管理数据的核心工具。随着数据量的不断增加和业务需求的复杂化，开发者和数据分析师需要掌握编写复杂查询、创建视图和存储过程的技能。这些技能不仅能够提高数据操作的效率，还能确保数据处理的准确性和安全性。复杂查询：能够从多个表中提取相关数据，进行联接、......
  • 洛谷 P2680 [NOIP2015 提高组] 运输计划 做题记录
    首先题目要求最大的最小，我们二分答案，对于每个答案，我们筛出比它长的路径，找到它们最长的公共边，删掉后验证正确性即可。找公共边可以用树上差分来做，时间复杂度\(O(m\logn\logV)\)，其中\(V\)是二分区间大小。你会发现你挂了一堆点，让我们来卡常：首先预处理出所有节点的\(dfn\)，每......
  • 【代码随想录Day50】图论Part02
    岛屿数量深搜题目链接/文章讲解：代码随想录classSolution{//计算网格中岛屿的数量publicintnumIslands(char[][]grid){intsum=0;//初始化岛屿数量为0//遍历整个网格for(inti=0;i<grid.length;i++){......
  • 【图论】（五）最短路径算法（D / BF / SPFA / F / A*）
    最短路径算法（D/BF/SPFA/F/A*）1.最短路径之dijkstra（D算法）思路模拟过程程序实现拓展2.dijkstra算法堆优化思路程序实现3.Bellman_ford算法（BF算法）松弛模拟过程拓展4.Bellman_ford队列优化算法（又名SPFA）模拟过程拓展5.Bellman_ford之判断负权回路思路拓展6......
  • 图论优化
    图论优化三元环计数首先给所有边定向，从度数小的点指向度数大的点，如果度数一样，则从编号小的指向编号大的，最终形成一张DAG。枚举\(u\)以及\(u\)指向的点\(v\)以及\(v\)指向的点\(w\)，如果\(u\)也指向\(w\)则成三元环。如果要一开始是有向图计数则最后判断一下\(u,v,w\)的方向即可......
  • P1040 [NOIP2003 提高组] 加分二叉树
    P1040[NOIP2003提高组]加分二叉树题目描述设一个\(n\)个节点的二叉树\(\text{tree}\)的中序遍历为\((1,2,3,\ldots,n)\)，其中数字\(1,2,3,\ldots,n\)为节点编号。每个节点都有一个分数（均为正整数），记第\(i\)个节点的分数为\(d_i\)，\(\text{tree}\)及它的每个子树都有一......
  • AOT漫谈专题(第六篇): C# AOT 的泛型,序列化,反射问题
    一：背景1.讲故事在.NETAOT编程中，难免会在泛型，序列化，以及反射的问题上纠结和反复纠错尝试，这篇我们就来好好聊一聊相关的处理方案。二：常见问题解决1.泛型问题研究过泛型的朋友应该都知道，从开放类型上产下来的封闭类型往往会有单独的MethodTable，并共用EEClass，对于值类型......
  • 【专题】概率期望
    前言期望的计算公式：\[E(X)=\sum_i{i\timesP(x=i)}\]期望的线性性：\[E(X+Y)=E(X)+E(Y),E(kX)=kE(X)\]百事世界杯之旅[SHOI2002]百事世界杯之旅题目描述假设有\(n\)个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？解：令\(f(i)\)表......
  • 提高组专题 dp4
    A[PA2021]OddeskidodeskiDP挺显然的，但我推错了……。\[\begin{split}dp_{i+1,j,1}&+=\sum(dp_{i,j,1}+dp_{i,j,0})\timesj\\dp_{i+1,j+1,0}&+=\sumdp_{i,j,1}\times(m-j)\\dp_{i+1,j,0}&+=\sumdp_{i,j,0}\times(m-j)\end{split}\]#include&......
  • 考公刷题，如何才能做到有效提高？
    在这个“不拼爹”的时代里，考公务员成了不少小伙伴们的首选。但是，要想在这条路上走得稳当，可不是一件容易的事儿。如何通过刷题来提升自己的竞争力呢？我们就来说说那些能让你刷题效率翻倍的小技巧吧！1.制定合理的学习计划刷题不是漫无目的地做题，而是要有计划地进行。想象一下，如......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99