1 条题解

  • 0
    @ 2025-8-24 21:13:48

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Daidly
    竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

    搬运于2025-08-24 21:13:47，当前版本为作者最后更新于2021-07-10 10:48:58，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    题目较简单，但代码较长。

    邻接矩阵和权矩阵

    两者差不多，只不过一个存是否有边 (0,1)(0,1)，一个存边权。

    使用一个二维数组 a 来表示。

    若为无权图，a[u][v]=1 表示存在 uu 到 vv 的边，a[u][v]=0 表示不存在。

    若为赋权图，a[u][v]=d 表示存储 uu 到 vv 的边的边权 dd。

    若为无向图，存两次即可。

    复杂度

    查询是否存在某条边：O(1)O(1)。

    遍历一个点的所有出边：O(n)O(n)。

    遍历整张图：O(n2)O(n^2)。

    空间复杂度：O(n2)O(n^2)。

    判断重边：

    bool f1=0;
if(a[u][v]>0)f1=1;

    在赋值 a[u][v] 前先查看 a[u][v] 之前是否被赋值过，若赋值过，则是有重边。

    邻接矩阵和权矩阵代码：

    void work1(){
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=n;++j){
    		cout<<a[i][j]<<" ";
		}cout<<endl;
	}
}

    关联矩阵

    使用一个二维数组 b 来表示。

    关联矩阵即用一个矩阵来表示各个点和每条边之间的关系，所以当图不是赋权图且无自环时，可以用关联矩阵表示。

    对于无向图：

    第 ii 条边 (u,v)(u,v) 可表示为：

    b[u][i]=1;
b[v][i]=1;

    若 b[u][i]=1，表示边 ii 上有点 uu。

    若 b[u][i]=0，表示边 ii 和点 uu 不相关联。

    对于有向图：

    第 ii 条边 (u,v)(u,v) 可表示为：

    b[u][i]=1;
b[v][i]=-1;

    若 b[u][i]=1，表示边 ii 离开点 uu。

    若 b[u][i]=-1，表示边 ii 进入点 uu。

    若 b[u][i]=0，表示边 ii 和点 uu 不相关联。

    判断自环：

    bool f2=0;
if(u==v)f2=1;

    看 uu 和 vv 是否是同一个点，若是，则有自环。

    关联矩阵代码：

    void work2(){
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=m;++j){
    		cout<<b[i][j]<<" ";
		}cout<<endl;
	}
}

    邻接表

    对于无权图：

    使用一个动态数组 vector<int>c1[MAXN]; 来表示。

    对于无向图:

    c1[u].push_back(v);
c1[v].push_back(u);

    对于有向图：

    c1[u].push_back(v);

    对于赋权图：

    由于要存两个数，考虑使用 pair<int,int>，使用一个动态数组 vector<pair<int,int> >c2[MAXN]; 来表示。

    其中 c2[i][j].first 表示第 ii 个点的第 jj 条边的对应点，c2[i][j].second 表示第 ii 个点的第 jj 条边的边权。

    对于无向图:

    c2[u].push_back(make_pair(v,d));
c2[v].push_back(make_pair(u,d));

    对于有向图：

    c2[u].push_back(make_pair(v,d));

    邻接表代码：

    void work3(){
	if(type2==0){
		for(int i=1;i<=n;++i){
			for(int j=0;j<c1[i].size();++j){
				cout<<c1[i][j]<<" ";
			}cout<<endl;
		}
	}else{
		for(int i=1;i<=n;++i){
			for(int j=0;j<c2[i].size();++j){
				cout<<c2[i][j].first<<" "<<c2[i][j].second<<" ";
			}cout<<endl;
		}
	}
}

    正向表

    用三个数组 A、B、Z 来表示。

    对于 A 数组，A[1]=1A[1]=1，A[i]=A[i−1]+c[i−1].size()A[i]=A[i-1]+c[i-1].size()。

    其中，c[i−1].size()c[i-1].size() 表示第 i−1i-1 个点的连点个数。

    注意 A 数组的点要到第 i+1i+1 个。

    对于 B、Z 数组，设长度为 numnum，初始为 00。

    B 数组负责存对应点，Z 数组负责存对应边权，长度一样（按照点的顺序和存对应点的顺序），可结合代码理解。

    正向表代码：

    void work4(){
	num=0,A[1]=1;
	if(type2==0){
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c1[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c1[i].size();++j){
				B[++num]=c1[i][j];
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
	}else{
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c2[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c2[i].size();++j){
				B[++num]=c2[i][j].first;
				Z[num]=c2[i][j].second;
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<Z[i]<<" ";
		}cout<<endl;
	}
}

    逆向表

    对于无向图，逆向表与正向表相同，不用输出。

    对于有向图：

    顾名思义，“逆”就是把顺序逆过来。

    • 对于无权图，使用一个动态数组 vector<int>c3[MAXN]; 来表示。

    例如：边 (u,v)(u,v)，可存为：c3[v].push_back(u);。

    • 对于赋权图，使用一个动态数组 vector<pair<int,int> >c4[MAXN]; 来表示。

    例如：边 (u,v)=d(u,v)=d，可存为：c4[v].push_back(make_pair(u,d));。

    其余与正向表类似，可结合代码理解。

    逆向表代码：

    void work5(){
	num=0,A[1]=1;
	if(type2==0){
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c3[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c3[i].size();++j){
				B[++num]=c3[i][j];
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
	}else{
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c4[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c4[i].size();++j){
				B[++num]=c4[i][j].first;
				Z[num]=c4[i][j].second;
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<Z[i]<<" ";
		}cout<<endl;
	}
}

    写在最后

    • 注意 11：正向表和逆向表的 B、Z 两个数组要开两倍 MAXN 大小，代码简用 MAXN<<1 来表示。

    • 注意 22：当一个点邻接表中没有连边时，也要换行，如样例二，应该是：

    
2 4
1 5 1 3
1 1 2 4
2 1 1
4 5 3
1 3 4 4
3 3 2
5 3 4

    总体代码如下：

    #include<bits/stdc++.h>
using namespace std;
#define MAXN 305
int n,m,u,v,d;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
vector<int>c1[MAXN];
vector<pair<int,int> >c2[MAXN];
vector<int>c3[MAXN];
vector<pair<int,int> >c4[MAXN];
int A[MAXN],B[MAXN<<1],num,Z[MAXN<<1];
bool type1,type2,f1,f2;
void work1(){
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=n;++j){
    		cout<<a[i][j]<<" ";
		}cout<<endl;
	}
}
void work2(){
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=m;++j){
    		cout<<b[i][j]<<" ";
		}cout<<endl;
	}
}
void work3(){
	if(type2==0){
		for(int i=1;i<=n;++i){
			for(int j=0;j<c1[i].size();++j){
				cout<<c1[i][j]<<" ";
			}cout<<endl;
		}
	}else{
		for(int i=1;i<=n;++i){
			for(int j=0;j<c2[i].size();++j){
				cout<<c2[i][j].first<<" "<<c2[i][j].second<<" ";
			}cout<<endl;
		}
	}
}
void work4(){
	num=0,A[1]=1;
	if(type2==0){
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c1[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c1[i].size();++j){
				B[++num]=c1[i][j];
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
	}else{
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c2[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c2[i].size();++j){
				B[++num]=c2[i][j].first;
				Z[num]=c2[i][j].second;
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<Z[i]<<" ";
		}cout<<endl;
	}
}
void work5(){
	num=0,A[1]=1;
	if(type2==0){
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c3[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c3[i].size();++j){
				B[++num]=c3[i][j];
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
	}else{
        for(int i=2;i<=n+1;++i){
		    A[i]=A[i-1]+c4[i-1].size();
	    }
		for(int i=1;i<=n;++i){
			for(int j=0;j<c4[i].size();++j){
				B[++num]=c4[i][j].first;
				Z[num]=c4[i][j].second;
			}
		}
		for(int i=1;i<=n+1;++i){
			cout<<A[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<B[i]<<" ";
		}cout<<endl;
		for(int i=1;i<=num;++i){
			cout<<Z[i]<<" ";
		}cout<<endl;
	}
}
int main(){
	cin>>n>>m>>type1>>type2;
	if(type2==0){
	    for(int i=1;i<=m;++i){
		    cin>>u>>v;
		    if(a[u][v]>0)f1=1;
		    if(u==v)f2=1;
		    if(type1==0){
		    	a[u][v]=1;
		    	a[v][u]=1;
	    	    b[u][i]=1;
	    	    b[v][i]=1;
		    	c1[u].push_back(v);
	    	    c1[v].push_back(u);
		    }else{
		    	a[u][v]=1;
		    	b[u][i]=1;
	    	    b[v][i]=-1;
		    	c1[u].push_back(v);
		    	c3[v].push_back(u);
	    	}
	    }
	    if(f1==0)work1();
	    if(f2==0)work2();
	    work3();
	    work4();
	    if(type1==1)work5();
	}else{
		for(int i=1;i<=m;++i){
			cin>>u>>v>>d;
			if(a[u][v]>0)f1=1;
			if(type1==0){
				a[u][v]=d;
				a[v][u]=d;
	    	    c2[u].push_back(make_pair(v,d));
	    	    c2[v].push_back(make_pair(u,d));
			}else{
				a[u][v]=d;
				c2[u].push_back(make_pair(v,d));
				c4[v].push_back(make_pair(u,d));
			}
		}
		if(f1==0)work1();
		work3();
		work4();
		if(type1==1)work5();
	}
	return 0;
}

    如果您看懂了或是对您有帮助，请点一个小小的赞吧，谢谢！

    • 1

    [图论与代数结构 101] 图的代数表示

    信息

    ID
    6850
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 33ms