首页 > 其他分享 >平面图学习笔记--zhengjun

平面图学习笔记--zhengjun

时间:2023-07-09 20:33:05浏览次数:39  
标签:return fa -- 平面图 zhengjun int vec const find

要点不多,记一下即可。

\(G\) 的对偶图记为 \(G^*\)。

  • \(G^*\) 为连通图,若 \(G\) 联通,则 \(G^{*}{^*}=G\)

  • \(G^*\) 中的简单环对应着 \(G\) 中的极小割,(简单对应极小),利用该性质,可以把平面图上的最小割问题转化为对偶图上的最短路问题

  • 平面图欧拉公式:\(V-E+F-C=1\),点数-边数+面数-联通块数=1

  • 平面图规模上限:\(E\le 3\times V-6,F\le 2\times V-4\)

  • 平面图点定位:使用扫描线+set 即可,实现不难,有点细节

  • 平面图求对偶图:对于每个点的出边极角排序即可

n 合 1 模板题:link

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10,K=__lg(N)+2,INF=1e9+1;
int q,V,E,F;
struct vec{
	int x,y;
}a[N];
vec operator - (const vec &a,const vec &b){
	return {a.x-b.x,a.y-b.y};
}
bool operator == (const vec &a,const vec &b){
	return a.x==b.x&&a.y==b.y;
}
int find(const vec &a){
	if(!a.y)return a.x>0?0:1;
	return a.y>0?0:1;
}
ll cross(const vec &a,const vec &b){
	return 1ll*a.x*b.y-1ll*a.y*b.x;
}
bool operator < (const vec &a,const vec &b){
	int x=find(a),y=find(b);
	return x^y?x<y:cross(a,b)>0;
}
struct edges{
	int v,w,id,to,nex;
}edge[N*2];
int kk=1,head[N];
void add(int u,int v,int w){
	edge[++kk]={v,w,0,0,head[u]},head[u]=kk;
	edge[++kk]={u,w,0,0,head[v]},head[v]=kk;
}
void read(int &x){
	char c;
	for(x=0;!isdigit(c=getchar()););
	for(;x=x*10+c-'0',isdigit(c=getchar()););
	if(x<<=1,c=='.')getchar(),x++;
}
struct edgs{
	int u,v,w;
};
vector<edgs>edg;
namespace DSU{
	int fa[N];
	void init(int n){
		iota(fa,fa+1+n,0);
	}
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	bool merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return 0;
		return fa[x]=y,1;
	}
}
vector<pair<int,int> >to[N];
void Add(int u,int v,int w){
	to[u].push_back({v,w}),to[v].push_back({u,w});
}
int dep[N],anc[K][N],mx[K][N];
#define v e.first
#define w e.second
void dfs1(int u,int fa=0){
	anc[0][u]=fa,dep[u]=dep[fa]+1;
	for(auto e:to[u])if(v^fa)mx[0][v]=w,dfs1(v,u);
}
#undef v
#undef w
int query(int u,int v){
	if(!~u||!~v)return INF;
	if(dep[u]<dep[v])swap(u,v);
	int ans=0;
	for(int x=dep[u]-dep[v];x;x^=x&-x){
		int i=__builtin_ctz(x);
		ans=max(ans,mx[i][u]),u=anc[i][u];
	}
	if(u==v)return ans;
	for(int i=__lg(dep[u]);~i;i--)
		if(anc[i][u]^anc[i][v]){
			ans=max({ans,mx[i][u],mx[i][v]});
			u=anc[i][u],v=anc[i][v];
		}
	return max({ans,mx[0][u],mx[0][v]});
}
int s[N],t[N];
int cnt,buf[N];
int now;
using big=__int128;
struct line{
	vec s,t;
	int id;
	big calc()const{
		return (1ll*s.y*(t.x-now)+1ll*t.y*(now-s.x));
	}
	int len()const{
		return t.x-s.x;
	}
	bool operator < (const line &x)const{
		if(s==x.s)return cross(t-s,x.t-s)>0;
		if(t==x.t)return cross(s-t,x.s-t)<0;
		big tmp=calc()*x.len()-x.calc()*len();
		if(tmp)return tmp<0;
		return id<x.id;
	}
};
set<line>S;
int k;
struct ques{
	int x,y,*ans;
}o[N*2];
vector<int>p[N];
int main(){
	freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d",&V,&E);
	for(int i=1;i<=V;i++)read(a[i].x),read(a[i].y);
	for(int i=1;i<=V;i++)buf[++cnt]=a[i].x;
	sort(buf+1,buf+1+cnt),cnt=unique(buf+1,buf+1+cnt)-buf-1;
	buf[cnt+1]=INF;
	for(int i=1;i<=V;i++)p[lower_bound(buf+1,buf+1+cnt,a[i].x)-buf].push_back(i);
	for(int i=1,u,v,w;i<=E;i++){
		scanf("%d%d%d",&u,&v,&w),add(u,v,w);
	}
	int id=1;
	for(int i=2;i<=V;i++)if(a[i].x>a[id].x)id=i;
	for(int u=1;u<=V;u++){
		vector<pair<int,int> >to;
		for(int i=head[u];i;i=edge[i].nex)to.push_back({edge[i].v,i});
		sort(to.begin(),to.end(),[&](pair<int,int>x,pair<int,int>y){
			return a[x.first]-a[u]<a[y.first]-a[u];
		});
		if(u==id)edge[to[0].second].id=-1;
		int len=to.size();
		for(int i=0;i<len;i++)edge[to[i].second^1].to=to[(i+1)%len].second;
	}
	for(int u=1;u<=V;u++){
		for(int i=head[u],j;i;i=edge[i].nex)if(!edge[i].id){
			F++;
			for(j=i;!edge[j].id;j=edge[j].to)edge[j].id=F;
			if(!~edge[j].id){
				for(F--,j=edge[j].to;~edge[j].id;j=edge[j].to)edge[j].id=-1;
			}
		}
	}
//	for(int u=1;u<=V;u++){
//		for(int i=head[u];i;i=edge[i].nex){
//			fprintf(stderr,"%d %d %d\n",u,edge[i].v,edge[i].id);
//		}
//	}
	for(int i=2;i<=kk;i+=2){
		if(~edge[i].id&&~edge[i+1].id)
			edg.push_back({edge[i].id,edge[i+1].id,edge[i].w});
	}
	sort(edg.begin(),edg.end(),[](edgs x,edgs y){return x.w<y.w;});
	DSU::init(F);
	for(edgs x:edg)if(DSU::merge(x.u,x.v))Add(x.u,x.v,x.w);
	for(int i=1;i<=F;i++)if(DSU::fa[i]==i)Add(0,i,INF);
	dfs1(0);
	for(int i=1;(1<<i)<=F;i++)
		for(int u=1;u<=F;u++){
			int t=anc[i-1][u];
			anc[i][u]=anc[i-1][t];
			mx[i][u]=max(mx[i-1][u],mx[i-1][t]);
		}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int x,y;
		read(x),read(y);
		o[++k]={x,y,&s[i]};
		read(x),read(y);
		o[++k]={x,y,&t[i]};
	}
	sort(o+1,o+1+k,[](ques x,ques y){return x.x<y.x;});
	for(int i=0,x=1;i<=cnt;i++){
		now=buf[i];
		for(int u:p[i]){
			for(int i=head[u];i;i=edge[i].nex){
				int v=edge[i].v;
				if(a[v].x<a[u].x)S.erase({a[v],a[u],edge[i^1].id});
			}
		}
		for(int u:p[i]){
			for(int i=head[u];i;i=edge[i].nex){
				int v=edge[i].v;
				if(a[v].x>a[u].x)S.insert({a[u],a[v],edge[i].id});
			}
		}
		for(;x<=k&&o[x].x>=buf[i]&&o[x].x<buf[i+1];x++){
			vec p={o[x].x,o[x].y};
			now=o[x].x;
			auto it=S.lower_bound({p,{p.x+1,p.y},0});
			if(it==S.end())*o[x].ans=-1;
			else *o[x].ans=it->id;
		}
	}
	for(int i=1;i<=q;i++){
		int ans=query(s[i],t[i]);
		if(ans>=INF)puts("-1");
		else printf("%d\n",ans);
	}
	return 0;
}

标签:return,fa,--,平面图,zhengjun,int,vec,const,find
From: https://www.cnblogs.com/A-zjzj/p/17539324.html

相关文章

  • Jenkins快速入门部署+实践
    安装方法一Jenkins中文网下载jenkins.war方法二直接从http://mirrors.jenkins-ci.org/war/latest/jenkins.war下载最新的war包,然后解压到某个固定目录就算安装完成了启动方式启动方法:java-jarjenkins.war即可打开浏览器进入链接http://localhost:8080如果安装过程......
  • Docker系列---【Docker和宿主机如何传输文件?】
    Docker和宿主机如何传输文件?前提:Docker正在运行,即dockerps命令能看到。宿主机传输文件到dockerdockercp<宿主机文件路径><容器ID或名称>:<容器内目标路径>#例:复制宿主机文件data.txt到容器目录/app/dockercp/host/data.txtmy-container:/app/data.txtdocker传输文......
  • 七、获取消息的方式
    RocketMQ获取消息的方式有两种:PULL(消费者主动去Broker拉取):拉取消息需要编写代码去Broker获取。通过DefaultMQPullConsumer,关联namesrv后,通过topic获取到关联的所有MessageQueue。遍历所有的MessageQueue,批量获取消息。并消费。直到处理完所有的MessageQueue。用户需要自己保......
  • 网络3️⃣QUIC
    快速UDP互联网连接(QuickUdpInternetConnection)......
  • Matlab-对wav音频文件DSB调制及解调
    1.读取wav音乐文件%读取音频文件filename='jay.wav';[sound_data,fs]=audioread(filename);%9507502x244100sound_data_1=sound_data(:,1);sound_data_1=sound_data_1';%转置sound_data有两列,因为此音乐文件有两个通道,音频采样率为44100;这......
  • OSPF报文更新机制与认证机制
    OSPFOSPF更新机制定时更新默认情况下,产生这条LSA的路由器每隔1800S,会更新自身产生的LSA触发更新当产生这条LSA的路由器发现这条LSA的参数发生了变化,会触发更新OSPF协议如何删除一条LSA发送一条LSU,其中seq不变,chksum不变,将Lsage设置为3600OSPF认证区域认证......
  • 43. 排序算法
    一、什么是排序  排序也称排序算法,排序是将一组数组,依指定的顺序进行排列的过程。排序分为内部排序和外部排序两种。内部排序是指将需要处理的所有数据都加载到内部存储器中进行排序。外部排序是指数据量过大,无法全部加载到内存中,需要借助外部存储进行排序。二、冒......
  • UML图
    声明:本设计模式系列内容大部分内容来源b站黑马程序员设计模式视频及其他大佬文章和自我总结b站黑马程序员设计模式目录UML图1.类图概述2.类图的作用3.类图表示法3.1类的表示方式3.2类与类之间关系的表示方式3.2.1关联关系3.2.2聚合关系3.2.3组合关系3.2.4依赖关系3.2.5......
  • Docker学习路线1:介绍
    Docker是什么?Docker是一个开源平台,通过将应用程序隔离到轻量级、可移植的容器中,自动化应用程序的部署、扩展和管理。容器是独立的可执行单元,封装了运行应用程序所需的所有必要依赖项、库和配置文件,可以在各种环境中稳定地运行。什么是容器?容器是一种轻量级、可移植和隔离的软件......
  • TypeScript 条件类型(Conditional Types)以及 infer 关键字
    什么是条件类型条件类型可以让程序根据输入的类型来决定输出的类型是什么,也就是说根据不同的输入类型来确定输出的类型。条件类型的形式有点类似于JS中的条件表达式(condition?trueExpression:falseExpression):file:[条件类型的规则]SomeTypeextendsOtherType?TrueTyp......