lemonoil

OI__nothing is impossible

图论专题

• 标签: 图论

四道模板题，就少些题解了，第一道题是并查集加维护，蓝书上写到过。第二道题是最短路，观察数据范围，SPFA明显优于DIj就完了，第三道题trajan缩点两次建图，第四道题就一道for了n次的最小生成树。

Problem 1. bricks

Input file: bricks.in Output file: bricks.out Time limit: 1 second jyb 在BUAA 天天被大神虐，所以只能去搬砖了。终于在2019 年的夏天，菜菜的jyb 找不到工作，真的去工地搬砖了。jyb 的工头cky 是一个很麻烦的人，他会让jyb 按某种方式搬砖，还问会问一些奇怪的问题。现在有n 块砖，m 次操作。操作有两种：

  1. M x y 把编号为x 的砖所在的一摞砖搬到编号为y 的砖所在的一摞砖的上面。如果x 和y 在同一摞砖则忽略这个操作。（最初，每块砖都是单独一摞）
  2. C x 询问x 下面压着多少块砖。 jyb 搬砖实在是太累了，想请你帮忙回答一下cky 工头的询问。 Input 第1 行，2 个整数n; m，表示一共有多少块砖以及有多少操作。 接下来m 行，每行一个操作，操作表示形式与前文一致。 Output 对于每次询问操作，输出答案 Sample bricks.in 6 6
    M 1 6
    C 1
    M 2 4 M 2 6 C 3 C 4 bricks.out 1 0 2 Note • 对于30% 的数据，1<=n,m<= \(10^3\) • 对于60% 的数据，1<=n<= \(10^4\) ,1<=m<= \(10^5\) • 对于100% 的数据，1<=n<= \(20^5\),1<=m<= \(30^6\)

题解——并查集

用链表什么的暴力枚举题意，最坏复杂度是O( \(m^2\) )的。 注意到每次都是移动一摞砖，其实问题就是集合的合并，只是这个集合是一个有序的，我们还需要知道每个元素在集合中的位置。我们可以利用并查集高效的来解决。我们引入一个dep数组，对于祖先节点（将每摞砖最上方的一块设为祖先，设最下面的为祖先也是可以的），我们记录该集合中一共有多少块砖，对于其他节点，我们记录它上方有多少块砖，这样我们可以很容易地计算出下方有多少块。这样在合并x和y（设他们祖先为 \(f_x\) ， \(f_y\) ）时，我们将dep[ \(f_x\) ]赋给dep[ \(f_y\) ]（因为移到了上方， \(f_x\) 有多少块 \(f_y\) 上方就有多少块），然后dep[ \(f_x\) ]要加上原本的dep[ \(f_y\) ]。难点就是在合并的过程中，dep数组怎么维护。其实很简单，只需要在路径压缩时顺带维护即可，如果一个节点x的祖先 \(f_x\) 不是祖先（即已被合并过），那么dep[x]加上dep[ \(f_x\) ]即可（等于头上又多了一摞砖，所以要加上）。 时间复杂度O( \(α()\) )

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<iostream>
#define NAME "bricks"
using namespace std;
inline int readin(){
    static char ch;int resez,flag=1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;resez=ch-48;
    while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ch-48;resez*=flag;
}
char c;
int x,y,n,m,fa[3000020][2];
int find(int x){
	if(x==fa[x][0])return x;
	else{
		int f=fa[x][0];
		fa[x][0]=find(fa[x][0]);
		if(fa[f][0]!=f)fa[x][1]+=fa[f][1];
		return fa[x][0];
	}
}
int main(){
	freopen(NAME".in","r",stdin);
	freopen(NAME".out","w",stdout);
	n=readin(),m=readin();
	for(register int i=1;i<=n;i++)fa[i][0]=i,fa[i][1]=1;
	for(register int i=1;i<=m;i++){
		scanf(" %s",&c);
		if(c=='M'){
			if((x=find(readin()))!=(y=find(readin()))){
				fa[y][0]=x,n=fa[y][1];
				fa[y][1]=fa[x][1];
				fa[x][1]+=n;
			}
		}else{
			if((x=readin())==fa[x][0])cout<<fa[x][1]-1<<endl;
			else y=find(x),cout<<fa[y][1]-fa[x][1]-1<<endl;
		}
	}
	return 0;
}

Problem 2. drive

Input file: drive.in Output file: drive.out Time limit: 2 second 工头 cky 最近开了一家贸易公司，开始经商。作为 cky 的忠实小弟，jyb 当了 cky 老总的司机。一天晚上，cky 突然找到了一个新的客户，所以第二天一早要急着从成都去上海谈生意（设全国一共有 n 个城市, 成都编号为 1，上海编号为 n），城市之间有高速公路，每条高速公路都有一个最高限速和长度。cky 想：我应该在今晚就告诉客户我最快多久能到上海，不然客户就可能先和别人谈生意了。所以他就让 jyb 计算一下最快多久能到。 jyb 作为一名经验丰富的老司机，看了一眼天气预报，天气预报说：全国范围内有一条高速公路第二天可能下大雨（大雨天气的话，车速会下降 75%），但坑爹的是居然不知道是哪一条，准确信息要第二天一早才知道。现在jyb 拥有全国高速公路图，为了回答一个尽量早但又不失信于客户的时间，jyb 想请你帮帮忙。 ps: 虽然cky 很急，但是他还是告诫jyb 不能超速行驶。第二天知道哪会下雨后，jyb 自然会作出正确的抉择。迟到肯定就是失信于客户啦！ Input 第1 行，2 个整数n; m，表示城市数和高速公路数。 接下来m行，每行4 个整数u; v; speed; length，表示该条高速公路连接的两个城市u; v，以及最高限速speed 和路长length。 Output 输出满足题意的时间，保留4 位小数。 Sample drive.in drive.out 3 3 4.0000 1 2 100 100 2 3 100 100 1 3 100 400 2 1 4.0000 1 2 100 100 Note • 对于30% 的数据，1<=n<= \(10^2\) ,1<=m<=\(10^3\) • 对于100% 的数据,1<=n<= \(4*10^3\) ,1<=m<= \(10^4\) ,60<=speed<=120,200<=length<=1000

题解——最短路

如果没有大雾天气，很显然就是求一个最短路就行了。但是由于大雾天气的存在，如果大雾天气出现在乐最短路的路径上，那么肯定不能按照最快的时间到达，如果这样的话很可能就失信与客户。所以我们就需要枚举最短路径上每条高速公路出现大雾天气的情况，再求最短路，可得一个最糟的情况，即得到在不失信于客户的前提下的最快时间。 注意到数据范围，每条高速公路的行驶时间最多相差10倍，spfa的时间复杂度的上界大概为O( \(kM\) )，k = 10，而朴素Dijkstra求一次最短路为稳定O( \(n^2\) )，总的最坏为O( \(n^3\) )，所以我们采用spfa或者堆优化Dijkstra算法(jyb写的STL堆优被卡了两个点)求最短路。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define NAME "drive"
const int N=4010;
const int M=20010;
inline int readin(){
    static char ch;int resez;
    while((ch=getchar())<'0'||ch>'9');resez=ch-48;
    while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ch-48;
    return resez;
}
struct edges{int u,v,next;double w;}edge[M];
int n,m,q[N],head,tail,u,v,hu[N],num,pre[N],vis[N];
double dis[N],tmp,len;
inline void addedge(int u,int v,double w){edge[++num].u=u;edge[num].v=v;edge[num].w=w;edge[num].next=hu[u];hu[u]=num;}
double spfa(bool flag){
	for(register int i=2;i<=n;i++)dis[i]=100000000.0;
	head=0;tail=q[0]=vis[1]=1;
	while(head!=tail){
		u=q[head];
		for(register int i=hu[u];i;i=edge[i].next){
			if(v=edge[i].v,dis[v]>dis[u]+edge[i].w){
				if(dis[v]=dis[u]+edge[i].w,flag)pre[v]=i;
				if(!vis[v]){
					vis[v]=1;
					q[tail]=v;
					tail=(tail+1)%n;
				}
			}
		}
		vis[u]=0;head=(head+1)%n;
	}
	return dis[n];
}
int main(){
	freopen(NAME".in","r",stdin);
	freopen(NAME".out","w",stdout);
	n=readin(),m=readin();
	for(register int i=1;i<=m;i++){
		u=readin(),v=readin();
		scanf("%lf%lf",&tmp,&len);
		addedge(u,v,len/tmp);
	}
	double ans=spfa(1);m=n;
	while(m!=1){
		edge[pre[m]].w*=4.0;
		ans=max(ans,spfa(0));
		edge[pre[m]].w/=4.0;
		m=edge[pre[m]].u;
	}
	printf("%.4lf\n",ans);
	return 0;
}

Problem 3. graph

Input file: graph.in Output file: graph.out Time limit: 1 second jyb 给大家讲过强连通分量，强连通分量中的任意两点之间都可以互相到达。这个条件感觉很苛刻，大部分图都不能满足。现在jyb 告诉你一个新的概念：单向连通图；如果有向图中，对于任意节点 \(v_1\) 和 \(v_2\) ，至少存在从 \(v_1\) 到 \(v_2\) 和从 \(v_2\) 到 \(v_1\) 的路径中的一条，则为单向连通图。现在给出若干个有向图，jyb 想问你它们是不是单向连通图。 Input 第1 行，1 个整数T, 表示数据组数，对于每组数据： 第1 行，2 个整数n; m，表示点数和边数 接下来m 行，每行2 个整数u,v, 表示u 到v 有一条单向边。题目保证u! = v Output 对于每组数据，如果是则输出”Yes”, 不是则输出”No”（均不含引号） Sample graph.in 2 3 2 1 3 2 3 3 2 1 2 2 3 graph.out No Yes Note • 对于30% 的数据,1 <=n <=100，1 m <= 100 • 对于100% 的数据,1 <=T <=5,1 <=n <=30000，1 <= m<= \(2 *10^5\) 。

题解——tarjan求SCC+拓扑排序

暴力做法：Floyd求任意两点连通性。（给了30%的分） 我们知道，对于在同一SCC中的两点，它们是互相可达的，这也意味着一个SCC中的所有点和其他点的连通性都是一样的，显然我们可以将原图缩点简化问题。经过tarjan缩点后，得到了一个DAG，我们很容易想到如果一个图“分叉”，那么分叉上的点肯定是互不可达的，所以原图必须是“一条链”。为什么对链打引号呢？是因为这条链不用很严格，比如1->2 2->3 3->4 1->4 2->4这样的图也是满足的，且可能还有重边，所以只用入度出度去判断的方法容易出错，dfs去走一条链的办法也比较麻烦（我没想出有什么简单的办法）。我们利用拓扑排序，若一直都是一个入度为0的点（队中至多有一个点），那么就是满足题意的。 Ps：可以先写一个floyd来对拍（因为时间代价很低） 时间复杂度O( \(n+m\))

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define NAME "graph"
#define clr(x) memset((x),0,sizeof(x))
using namespace std;
const int N=100010;
const int M=400010;
inline int readin(){
    static char ch;int resez;
    while((ch=getchar())<'0'||ch>'9');resez=ch-48;
    while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ch-48;
    return resez;
}
struct edge{int v,next;}edge[M];
int T,hu[N][2],num,tot,top,cnt,numm,Q[N],head,tail,u,v,n,m,P[N],temp[N],low[N],vis[N],stack[N],fa[N];
void dfs(int u,int v=0){
	temp[u]=low[u]=++tot;
	vis[u]=1;stack[++top]=u;
	for(register int i=hu[u][0];i!=0;i=edge[i].next)
		if(v=edge[i].v,!temp[v])dfs(v),low[u]=min(low[v],low[u]);
		else if(vis[v]&&temp[v]<low[u])low[u]=temp[v];
	if(temp[u]==low[u]){
		cnt++;
		while(1){
			int x=stack[top--];
			vis[x]=0;
			fa[x]=cnt;
			if(x==u)break;
		}
	}
}
inline void addedge(int u,int v,int d){edge[++num].v=v;edge[num].next=hu[u][d];hu[u][d]=num;}
int main(){
	freopen(NAME".in","r",stdin);
	freopen(NAME".out","w",stdout);
	T=readin();
	while(T--){
		n=readin(),m=readin();
		num=cnt=tot=0;
		clr(hu),clr(temp),clr(P),clr(low);
		while(m--)addedge(readin(),readin(),0);
		for(register int i=1;i<=n;i++)if(!temp[i])dfs(i);
		for(register int i=1;i<=n;i++)
			for(register int j=hu[i][0];j;j=edge[j].next)
				if(fa[i]!=fa[edge[j].v]){
					P[fa[edge[j].v]]++;
					addedge(fa[i],fa[edge[j].v],1);
				}
		int ans=1;head=tail=0;
		for(register int i=1;i<=cnt;i++)if(!P[i])Q[tail++]=i;
		while(head<tail){
			if(tail-head>1){
				ans=0;break;
			}u=Q[head];
			for(register int i=hu[u][1];i;i=edge[i].next)
				if(v=edge[i].v,P[v]--,P[v]==0)Q[tail++]=v;
			++head;
		}
		if(ans)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

Problem 4. airplane

Input file: airplane.in Output file: airplane.out Time limit: 1 second cky 公司的运营蒸蒸日上，由于出差实在太频繁，而且坐汽车有些太慢了，所以 cky 想要顺势直接进驻航空业。cky 所在的国家天朝有 n 个城市，m 个航空公司，每两个城市之间可能有一条航线运营（双向），一共有k 条航线，每条航线都属于某一航空公司。现在cky 希望收购一家航空公司（为了涉足航空业以及防垄断，cky 必须且只能购买一家航空公司），使得他能通过飞机从任意城市到达目的城市（允许转机），当然很可能没有一家公司能满足cky 的要求，所以cky 还需收购其他公司掌控的航线。每个航空公司都有一个市值，每条航线都有一个收购价。现在cky 想知道他最少需要花费多少钱。 Input 第1 行，3 个整数n; m;k，表示城市数量，航空公司数和航线数。城市用1; 2; ……; n 编号。接下来一行，一共 m 个整数，第 i 个整数 \( a_i \) 表示第 i 个航空公司的市值。接下来 k 行，每行 4 个整数 \(u_i, v_i,cost_i,b_i\)。表示第i 条航线连接城市u,v，价值cost，所属航空公司为b。题目保证u! = v题目保证有解。 Output 输出最少需要花费多少钱。 Sample airplane.in 4 3 3 100 150 200 1 2 100 1 1 3 160 2 1 4 220 3 airplane.out 460 Note • 对于50% 的数据，1<= n<= 1000，1<= m<= 1000，1<= k <= 10000； • 对于100% 的数据，1<= n <= 2000，1 <= m <=2000，1<= k<= 200000, \( 1<=b_i<=m,1<=cost_i,a_i<=10^8\) 。

题解——最小生成树

最朴素的做法：枚举航空公司，将本公司的航线加入，然后做一遍MST，时间复杂度是O( \(klog_k+mk\) )的。 但我们注意到“在最小生成树中任意一条边都是连接两个集合边权最小的一条边”，这个是MST一个非常重要的结论，是Prim和kruscal算法中贪心的核心。利用这条性质我们可以知道，对于每个航空公司，我们只需要原图MST中得到的航线即可得到最优购买方案。所以更优的做法是：先跑一次MST，把得到的边记录下来，然后枚举航空公司，还是先讲本公司的边全部加进去，然后只用扫一边第一次MST中记录下来的边，用kruscal的方法去构造树即可。时间复杂度为O( \(klog_k+nm \) )。 对于本题，50%的数据是可以O(mk)过的，最后30%的数据我特别构造了一下,必须枚举到排序后的最后几条边才能构造出一颗生成树，所以O( \(mk\) )应该是过不了的，此外的20%数据是随机数据，加了构造出树就跳出判断的代码可能会过（但是jyb写的mk的没过。。）；另外，50%的数据需要long long

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <algorithm>
#define ll long long 
#define NAME "airplane" 
using namespace std;
const int M=200002;
const int N=2002;
const ll INF=1ll<<60;
template<class T>inline void readin(T &resez){
    static char ch;
    while((ch=getchar())<'0'||ch>'9');resez=ch-48;
    while((ch=getchar())>='0'&&ch<='9')resez=resez*10+ch-48;
}
struct data{
	int u,v;ll w;
	bool operator < (const data &rhs)const{
		return w<rhs.w;
	}
}dis[M],mst[N];
struct edges{
	int u,v,next;
}edge[M];
int hu[N],num,fa[N],n,m,k,cnt,u,v,tmp,w;
ll ans,a[N];
inline void addedge(int tmp,int u,int v){edge[++num].u=u;edge[num].v=v;edge[num].next=hu[tmp];hu[tmp]=num;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	freopen(NAME".in","r",stdin);
	freopen(NAME".out","w",stdout);
	readin(n),readin(m),readin(k);
	for(register int i=1;i<=m;i++)readin(a[i]);
	for(register int i=1;i<=k;i++){
		readin(dis[i].u),readin(dis[i].v),readin(dis[i].w),readin(tmp);
		addedge(tmp,dis[i].u,dis[i].v);
	}
	sort(dis+1,dis+1+k);
	for(register int i=1;i<=n;i++)fa[i]=i;
	for(register int i=1;i<=k;i++){
		int x=find(dis[i].u),y=find(dis[i].v);
		if(x!=y){
			fa[y]=x;
			mst[++cnt]=dis[i];
		}
	}
	ans=INF;
	for(register int i=1;i<=m;i++){
		for(register int j=1;j<=n;j++)fa[j]=j;
		for(register int j=hu[i];j;j=edge[j].next){
			int x=find(edge[j].u),y=find(edge[j].v);
			if(x!=y)fa[y]=x;
		}
		ll tot=0;
		for(register int j=1;j<=cnt;j++){
			int x=find(mst[j].u),y=find(mst[j].v);
			if(x!=y){
				fa[y]=x;
				tot+=mst[j].w;
			}
		}
		ans=min(ans,tot+a[i]);
	}
	printf("%I64d\n",ans);
	return 0;
}

click it and link me

Launch CodeCogs Equation Editor