《进阶指南》0x60 图论

0x6B 总结与练习

图论的总结与练习,题目有点多。

书本练习

观光 Sightseeing

提示:最短路 / 单源次短路及其条数

题目描述

比荷卢经济联盟有很多公交线路。每天公共汽车都会从一座城市开往另一座城市。沿途汽车可能会在一些城市(零或更多)停靠。

旅行社计划旅途从 \(S\) 城市出发,到 \(F\) 城市结束。由于不同旅客的景点偏好不同,所以为了迎合更多旅客,旅行社将为客户提供多种不同线路。

现在给定比荷卢经济联盟的公交路线图以及两个城市 \(S\) 和 \(F\),请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

数据范围

\(2\leq N\leq 10^3\),\(1\leq M\leq 10^4\),\(1\leq L\leq 10^3\),\(1\leq A,B,S,F\leq N\)。

题解

显然只要求出最短路和比最短路大 $1$ 的路径方案数。使用 \(\texttt{dijkstra}\) 算法即可以 \(\Theta(n\log_2m)\) 的时间复杂度解决本题。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXN=1e3+5;
const int MAXM=1e4+5;

int n,m;
int cnt,head[MAXN],to[MAXM],w[MAXM],Next[MAXM];

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

struct Node{
    int id,val;
    inline Node(reg int id=0,reg int val=0):id(id),val(val){
        return;
    }
    inline bool operator<(const Node& a)const{
        return val<a.val;
    }
    inline bool operator>(const Node& a)const{
        return val>a.val;
    }
};

bool vis[MAXN];
int dis[MAXN][2];
int sum[MAXN][2];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

inline void Dijkstra(reg int s){
    memset(dis,0x3f,sizeof(dis));
    memset(sum,0x00,sizeof(sum));
    dis[s][0]=0,sum[s][0]=1,Q.push(Node(s,0));
    while(!Q.empty()){
        static Node s;
        s=Q.top();
        Q.pop();
        reg int u=s.id,k=-1;
        if(dis[u][0]==s.val)
            k=0;
        if(dis[u][1]==s.val)
            k=1;
        if(k==-1)
            continue;
        for(reg int i=head[u];i;i=Next[i]){
            reg int v=to[i];
            reg int val=s.val+w[i];
            if(dis[v][0]>val){
                dis[v][1]=dis[v][0],sum[v][1]=sum[v][0];
                dis[v][0]=val,sum[v][0]=sum[u][k];
                Q.push(Node(v,val));
            }
            else if(dis[v][0]==val)
                sum[v][0]+=sum[u][k];
            else if(dis[v][1]>val){
                dis[v][1]=val;
                sum[v][1]=sum[u][k];
                Q.push(Node(v,val));
            }
            else if(dis[v][1]==val)
                sum[v][1]+=sum[u][k];
        }
    }
    return;
}

int main(void){
    int T;
    scanf("%d",&T);
    while(T--){
        cnt=0,memset(head,0,sizeof(head));
        scanf("%d%d",&n,&m);
        for(reg int i=1;i<=m;++i){
            static int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            Add_Edge(a,b,c);
        }
        int S,T;
        scanf("%d%d",&S,&T);
        Dijkstra(S);
        if(dis[T][0]==dis[T][1]-1)
            printf("%d\n",sum[T][0]+sum[T][1]);
        else
            printf("%d\n",sum[T][0]);
    }
    return 0;
}

升降梯上

提示:最短路 / 节点扩展到二维

题目描述

开启了升降梯的动力之后,探险队员们进入了升降梯运行的那条竖直的隧道,映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。

Nescafé 之塔一共有 \(N\) 层,升降梯在每层都有一个停靠点。

手柄有 \(M\) 个控制槽,第 \(i\) 个控制槽旁边标着一个数 \(C_i\),满足 \(C_1<C_2<C_3<\cdots<C_M\)。

如果 \(C_i>0\),表示手柄扳动到该槽时,电梯将上升 \(C_i\) 层;如果 \(C_i<0\),表示手柄扳动到该槽时,电梯将下降 \(−C_i\) 层;并且一定存在一个 \(C_i=0\),手柄最初就位于此槽中。

注意升降梯只能在 \(1\sim N\) 层间移动,因此扳动到使升降梯移动到 \(1\) 层以下、\(N\) 层以上的控制槽是不允许的。

电梯每移动一层,需要花费 \(2\) 秒钟时间,而手柄从一个控制槽扳到相邻的槽,需要花费 \(1\) 秒钟时间。

探险队员现在在 \(1\) 层,并且想尽快到达 \(N\) 层,他们想知道从 \(1\) 层到 \(N\) 层至少需要多长时间?

数据范围

\(1\leq N\leq 10^3\),\(2\leq M\leq 20\),\(-N<C_1<C_2<\cdots<C_M<N\)。

题解

显然可以直接分层图最短路,使用 \(\texttt{dijkstra}\) 算法的时间复杂度为 \(\Theta(nm\log_2nm)\),可以通过本题。

但是我们不难发现,如果显然层数之差的绝对值小于等于它们之间的最短路,我们不妨使用 \(\texttt{A}^{\ast}\) 算法来优化,时间复杂度不变,但时间效率更加优秀。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const int MAXN=1e3+5;
const int MAXM=20+5;

int n,m;
int c[MAXM];

inline bool check(reg int u){
	return 1<=u&&u<=n;
}

struct Node{
	int u,v;
	int f,h;
	inline Node(reg int u=0,reg int v=0,reg int f=0,reg int h=0):u(u),v(v),f(f),h(h){
		return;
	}
	inline bool operator<(const Node& a)const{
		return f+h<a.f+a.h;
	}
	inline bool operator>(const Node& a)const{
		return f+h>a.f+a.h;
	}
};

int dis[MAXM][MAXN];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

int main(void){
	n=read(),m=read();
	reg int p=-1;
	for(reg int i=1;i<=m;++i){
		c[i]=read();
		if(!c[i])
			p=i;
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1][p]=0,Q.push(Node(1,p,0,(n-1)*2));
	while(!Q.empty()){
		static Node s;
		s=Q.top();
		Q.pop();
		reg int u=s.u,v=s.v,f=s.f,h=s.h;
		if(dis[v][u]<f)
			continue;
		if(u==n){
			printf("%d\n",f);
			return 0;
		}
		reg int fu=u+c[v];
		if(check(fu)&&dis[v][fu]>f+2*abs(c[v])){
			dis[v][fu]=f+2*abs(c[v]);
			Q.push(Node(fu,v,f+2*abs(c[v]),(n-u-c[v])*2));
		}
		if(v>1&&dis[v-1][u]>f+1){
			dis[v-1][u]=f+1;
			Q.push(Node(u,v-1,f+1,h));
		}
		if(v<m&&dis[v+1][u]>f+1){
			dis[v+1][u]=f+1;
			Q.push(Node(u,v+1,f+1,h));
		}
	}
	puts("-1");
	return 0;
}

GF 和猫咪的玩具

提示:最短路 / 任意两点间最短路

题目描述

GF 同学和猫咪得到了一个特别的玩具,这个玩具由 \(n\) 个金属环(编号为 \(1\sim n\)),和 \(m\) 条绳索组成,每条绳索连接两个不同的金属环,并且长度相同。

GF 左手拿起金属环 \(L\),猫咪右手(或者说:爪)拿起金属环 \(R\)(\(L\) 不等于 \(R\)),然后尽量的向两边拉,他希望选择合适的 \(L\) 和 \(R\),使得被拉紧的绳索尽量的多。

当两个环之间有几个绳索数相等的连接方法时,只算其中一条连接方法拉紧,不算全部拉紧。

数据范围

\(2\leq n\leq 100\)。

题解

如果把绳索看作边权为 \(1\) 的边,那么显然,如果 \(L,R\) 确定,那么 \(L,R\) 拉紧后的绳索数量为 \(L,R\) 之间的最短路。

所以我们可以使用 \(\texttt{floyd}\) 算法求解多源最短路,然后取两点间最短路的最大值即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=100+5;
const int inf=0x3f3f3f3f;

int n,m;
int G[MAXN][MAXN];

int main(void){
	memset(G,0x3f,sizeof(G));
	n=read(),m=read();
	for(reg int i=1;i<=m;++i){
		static int a,b;
		a=read(),b=read();
		G[a][b]=G[b][a]=1;
	}
	for(reg int k=1;k<=n;++k)
		for(reg int i=1;i<=n;++i)
			for(reg int j=1;j<=n;++j)
				G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
	int ans=0;
	for(reg int i=1;i<=n;++i)
		for(reg int j=1;j<=n;++j)
			if(G[i][j]<inf)
				ans=max(ans,G[i][j]);
	printf("%d\n",ans);
	return 0;
}

社交网络

提示:最短路 / 任意两点间最短路及其条数

题目描述

在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象。

不妨看这样的一个问题。

在一个社交圈子里有 \(n\) 个人,人与人之间有不同程度的关系。

我们将这个关系网络对应到一个 \(n\) 个结点的无向图上,两个不同的人若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值 \(c\),\(c\) 越小,表示两个人之间的关系越密切。

我们可以用对应结点之间的最短路长度来衡量两个人 \(s\) 和 \(t\) 之间的关系密切程度,注意到最短路径上的其他结点为 \(s\) 和 \(t\) 的联系提供了某种便利,即这些结点对于 \(s\) 和 \(t\) 之间的联系有一定的重要程度。

我们可以通过统计经过一个结点 \(v\) 的最短路径的数目来衡量该结点在社交网络中的重要程度。

考虑到两个结点 \(A\) 和 \(B\) 之间可能会有多条最短路径。

我们修改重要程度的定义如下:令 \(C_{s,t}\) 表示从 \(s\) 到 \(t\) 的不同的最短路的数目,\(C_{s,t(v)}\) 表示经过 \(v\) 的从 \(s\) 到 \(t\) 的最短路的数目;

则定义
\[I(v)=\sum_{s\ne v,t\ne v}\frac{C_{s,t(v)}}{C_{s,t}}\]

为结点 \(v\) 在社交网络中的重要程度。

为了使 \(I(v)\) 和 \(C_{s,t(v)}\) 有意义,我们规定需要处理的社交网络都是连通的无向图,即任意两个结点之间都有一条有限长度的最短路径。

现在给出这样一幅描述社交网络的加权无向图,请你求出每一个结点的重要程度。

数据范围

\(n\leq 100\),\(m\leq 4500\),\(c\leq 10^3\)。

题解

显然可以直接用 \(\texttt{floyd}\) 算法得出答案,时间复杂度为 \(\Theta(n^3)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=100+5;

int n,m;
int dis[MAXN][MAXN];
ll cnt[MAXN][MAXN];

int main(void){
	n=read(),m=read();
	memset(dis,0x3f,sizeof(dis));
	for(reg int i=1;i<=m;++i){
		static int a,b,c;
		a=read(),b=read(),c=read();
		dis[a][b]=dis[b][a]=c;
		cnt[a][b]=cnt[b][a]=1;
	}
	for(reg int k=1;k<=n;++k)
		for(reg int i=1;i<=n;++i)
			if(k!=i)
				for(reg int j=1;j<=n;++j)
					if(i!=j&&j!=k){
						if(dis[i][k]+dis[k][j]==dis[i][j])
							cnt[i][j]+=cnt[i][k]*cnt[k][j];
						else if(dis[i][k]+dis[k][j]<dis[i][j]){
							dis[i][j]=dis[i][k]+dis[k][j];
							cnt[i][j]=cnt[i][k]*cnt[k][j];
						}
					}
	for(reg int k=1;k<=n;++k){
		reg double ans=0;
		for(reg int i=1;i<=n;++i)
			if(k!=i)
				for(reg int j=1;j<=n;++j)
					if(i!=j&&j!=k&&cnt[i][j])
						if(dis[i][k]+dis[k][j]==dis[i][j])
							ans+=cnt[i][k]*cnt[k][j]*1.0/cnt[i][j];
		printf("%.3lf\n",ans);
	}
	return 0;
}

北极网络 Arctic Network

提示:最小生成树

题目描述

国防部(DND)希望通过无线网络连接几个北部前哨站。

在建立网络时将使用两种不同的通信技术:每个前哨站都有一个无线电收发器,一些前哨站还有一个通信卫星。

任意两个拥有通信卫星的前哨站不论它们的位置如何,都可以通过卫星进行通信。

而如果利用无线电进行通信,则需要两个前哨站的距离不能超过 \(D\) 方可进行通信。

而 \(D\) 的大小取决于收发器的功率,收发器的功率越大,\(D\) 也就越大,但是需要的成本也就越高。

出于采购和维护的考虑,所有的前哨站都采用相同的收发器,也就是说所有前哨站的无线电通信距离 \(D\) 都是相同的。

你需要确定在保证任意两个前哨站之间都能进行通信(直接或间接)的情况下,\(D\) 的最小值是多少。

数据范围

\(1\leq S\leq 100\),\(S\leq P\leq 500\),\(0\leq x,y\leq 10^4\)。

题解

不难发现,我们可以直接把 \(S\) 颗卫星放在边权最大的点之间,然后我们只需要求解一个最小生成森林即可,等价于求最小生成树,直接用 \(\texttt{Kruskal}\) 算法即可求解。

#include<cstdio>
#include<cmath>
#include<algorithm>
using std::max;
using std::sort;

const int MAXP=500+5;

struct UnionFind{
	int ID[MAXP];
	void Init(int n){
		register int i;
		for(i=1;i<=n;++i)
			ID[i]=i;
		return;
	}
	int find(int x){
		if(x==ID[x])
			return x;
		else
			return ID[x]=find(ID[x]);
	}
	void merge(int a,int b){
		register int ra=find(a),rb=find(b);
		if(ra!=rb)
			ID[rb]=ra;
		return;
	}
	bool search(int a,int b){
		return find(a)==find(b);
	}
};

struct Node{
	int f,t;
	double dis;
	Node(void){
		f=t=dis=0;
		return;
	}
	Node(int a,int b,double c){
		f=a,t=b,dis=c;
		return;
	}
	bool operator<(const Node&a)const{
		return dis<a.dis;
	}
};

int N;
int S,P;
int x[MAXP],y[MAXP];
int cnt;
double ans;
Node E[MAXP*(MAXP-1)];
UnionFind A;

double dis(int,int);

int main(void){
	register int i,j,sum;
	scanf("%d",&N);
	while(N--){
		cnt=0;
		scanf("%d%d",&S,&P);
		for(i=1;i<=P;++i)
			scanf("%d%d",&x[i],&y[i]);
		for(i=1;i<=P;++i)
			for(j=i+1;j<=P;++j)
				E[++cnt]=Node(i,j,dis(i,j));
		sort(E+1,E+cnt+1);
		sum=0;
		ans=0;
		A.Init(P);
		for(i=1;i<=cnt&&sum<P-S;++i){
			if(!A.search(E[i].f,E[i].t)){
				++sum;
				ans=max(ans,E[i].dis);
				A.merge(E[i].f,E[i].t);
			}
		}
		printf("%.2f\n",ans);
	}
	return 0;
}


double dis(int a,int b){
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

四叶草魔杖

提示:最小生成树 / 状态压缩动态规划

题目描述

魔杖护法 Freda 融合了四件武器,于是魔杖顶端缓缓地生出了一棵四叶草,四片叶子幻发着淡淡的七色光。

圣剑护法 rainbow 取出了一个圆盘,圆盘上镶嵌着 \(N\) 颗宝石,编号为 \(0\sim N-1\)。

第 \(i\) 颗宝石的能量是 \(A_i\)。

如果 \(A_i>0\),表示这颗宝石能量过高,需要把 \(A_i\) 的能量传给其它宝石;如果 \(A_i<0\),表示这颗宝石的能量过低,需要从其它宝石处获取 \(-A_i\) 的能量。

保证 \(\sum A_i=0\)。

只有当所有宝石的能量均相同时,把四叶草魔杖插入圆盘中央,才能开启超自然之界的通道。

不过,只有 \(M\) 对宝石之间可以互相传递能量,其中第 \(i\) 对宝石之间无论传递多少能量,都要花费 \(T_i\) 的代价。

探险队员们想知道,最少需要花费多少代价才能使所有宝石的能量都相同?

数据范围

\(2\leq N\leq 16\),\(0\leq M\leq \frac{N(N-1)}{2}\),\(0\leq p_i,q_i<N\),\(-10^3\leq A_i\leq 10^3\),\(0\leq T_i\leq 10^3\)。

题解

不难发现,最后的分配方案必然是一或者多个连通块内部互相连边传递能量,且各个连通块满足 \(\sum A_i=0\)。

我们不妨考虑用背包 \(\texttt{dp}\) 进行状态合并,具体地,对于一个选取集合 \(S\),状态转移方程为:
\[\texttt{dp}_S=\min_{\texttt{sub}\subset S}\{\texttt{dp}_{\texttt{sub}}+\texttt{val}_{S-\texttt{sub}}\}\]

其中 \(\texttt{val}_{S-\texttt{sub}}\) 表示 \(\texttt{sub}\) 对 \(S\) 的补集代表的连通块传递能量的代价,用最小生成树的 \(\texttt{Kruskal}\) 算法预处理即可。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

inline void cMin(reg int &a,reg int b){
	if(a>b)
		a=b;
	return;
}

inline int lowbit(reg int x){
	return x&(-x);
}

const int MAXN=16;
const int MAXM=MAXN*(MAXN-1)/2;
const int inf=0x3f3f3f3f;

struct Edge{
	int u,v,w;
	inline Edge(reg int u=0,reg int v=0,reg int w=0):u(u),v(v),w(w){
		return;
	}
	inline bool operator<(const Edge &a)const{
		return w<a.w;
	}
};

int n,m;
int a[MAXN];
Edge E[MAXM];
int fa[MAXN];
int Lg[1<<MAXN],sum[1<<MAXN],val[1<<MAXN];
int dp[1<<MAXN];

inline int find(reg int x){
	if(x==fa[x])
		return x;
	else
		return fa[x]=find(fa[x]);
}

inline int Kruskal(reg int S){
	reg int tot=0,sum=0;
	for(reg int i=S;i;i^=lowbit(i)){
		reg int x=Lg[lowbit(i)];
		++tot;
		fa[x]=x;
	}
	reg int cnt=tot;
	for(reg int i=0;i<m&&cnt>1;++i)
		if(((S>>E[i].u)&1)&&((S>>E[i].v)&1)){
			reg int ra=find(E[i].u),rb=find(E[i].v);
			if(ra!=rb){
				--cnt;
				sum+=E[i].w;
				fa[rb]=ra;
			}
		}
	if(cnt==1)
		return sum;
	else
		return -1;
}

int main(void){
	n=read(),m=read();
	for(reg int i=0;i<n;++i)
		a[i]=read();
	for(reg int i=0;i<m;++i)
		E[i].u=read(),E[i].v=read(),E[i].w=read();
	sort(E,E+m);
	reg int U=(1<<n)-1;
	Lg[0]=-1;
	for(reg int i=1;i<=U;++i)
		Lg[i]=Lg[i>>1]+1;
	for(reg int S=0;S<=U;++S)
		for(reg int i=S;i;i^=lowbit(i)){
			reg int x=Lg[lowbit(i)];
			sum[S]+=a[x];
		}
	for(reg int S=0;S<=U;++S)
		if(!sum[S])
			val[S]=Kruskal(S);
		else
			val[S]=-1;
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(reg int S=0;S<=U;++S)
		if(!sum[S]){
			if(val[S]!=-1)
				dp[S]=val[S];
			for(reg int sub=S&(S-1);sub;sub=S&(sub-1))
				if(val[S^sub]!=-1)
					cMin(dp[S],dp[sub]+val[S^sub]);
		}
	if(dp[U]==inf)
		puts("Impossible");
	else
		printf("%d\n",dp[U]);
	return 0;
}

直径

Pages: 1 2 3 4 5 6 7 8 9 10 11 12