网站建设里的知识,找别人做公司网站第一步做什么,查排名的软件有哪些,wordpress编辑器商品模板洛谷B3643 - 图的存储
题目描述
给定一个 n n n 个顶点 m m m 条边的无向图。请以邻接矩阵和邻接表的形式输出这一张图。
输入格式
第一行输入两个正整数 n n n 和 m m m#xff0c;表示图的顶点数和边数。
第二行开始#xff0c;往后 m m m 行#xff0c;每行输入…洛谷B3643 - 图的存储
题目描述
给定一个 n n n 个顶点 m m m 条边的无向图。请以邻接矩阵和邻接表的形式输出这一张图。
输入格式
第一行输入两个正整数 n n n 和 m m m表示图的顶点数和边数。
第二行开始往后 m m m 行每行输入两个以空格隔开的正整数 u , v u,v u,v表示 u , v u,v u,v 顶点之间有一条边直接相连。
输出格式
首先输出 n n n 行 n n n 列的矩阵以空格隔开每一行之间的数表示邻接矩阵。第 i i i 行第 j j j 列的数为 1 1 1 则表示顶点 i , j i,j i,j 之间有一条边直接相连若为 0 0 0 则表示没有直接相连的边。
再往后输出 n n n 行。第 i i i 行首先先输出一个整数 d i d_i di表示这个顶点的度数再按照从小到大的顺序依次输出与顶点 i i i 直接相连的所有顶点。
样例 #1
样例输入 #1
5 5
1 2
2 3
3 5
1 3
3 4样例输出 #1
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
2 2 3
2 1 3
4 1 2 4 5
1 3
1 3提示
样例的图如图所示
数据保证对于所有数据 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105且图无重边无自环。 拿到这题我本来想快刀斩乱麻直接套模板做结果老老实实打了很久图的邻接矩阵存储和邻接表存储最后过了样例但是全 W A WA WA给我气晕了。各种抠细节之后也只对了三个点麻了。 洛谷的 B B B题库不给看样例标程也不给看代码的因为要卖课……
知识点链接图的存储与基本操作
总之先放出这段代码吧希望有缘人看到能指点一下我。 2024 / 06 / 01 3 : 50 : 49 2024/06/01\ 3:50:49 2024/06/01 3:50:49更新三点半的时候灵机一动想到了怎么改代码已经AC。错误代码放在这里警示后人更正的满分代码放在文末。
以下是30pts的代码
//30pts(WA)
#define _CRT_SECURE_NO_WARNINGS 1
#includecmath
#includecstdio
#includecstdlib
#includecstring
#includeiostream
#includealgorithm
using namespace std;#define MaxVertexNum 1007
#define MaxMGSize 500007
typedef char VertexType;
typedef int EdgeType;/*
typedef struct {VertexType Vex[MaxVertexNum];EdgeType Edge[MaxVertexNum][MaxVertexNum];
}MGraph;
*/typedef struct ArcNode {int adjvex;struct ArcNode* nextarc;
}ArcNode,* ArcList;
typedef struct VNode {VertexType data;ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {AdjList vertices;
}ALGraph;int vexnum, arcnum;
int MGraph[MaxMGSize] { 0 };inline void Init(ALGraph G) {
// memset(MGraph, 0, sizeof(MGraph));for (int i 1; i vexnum; i) {ArcList h (ArcList)malloc(sizeof(ArcList));h-adjvex 0;h-nextarc NULL;G.vertices[i].data 0;G.vertices[i].firstarc h;}return;
}inline int Get_K(int i, int j) {if (i j)swap(i, j);return i * (i - 1) / 2 j - 1;//对称矩阵压缩存储下三角
}inline void MG_Insert(int i, int j) {if (i j)swap(i, j);MGraph[Get_K(i, j)] 1;return;
}inline void MG_Print() {for (int i 1; i vexnum; i) {for (int j 1; j vexnum; j) {printf(%d, MGraph[Get_K(i, j)]);if (j ! vexnum)printf( );}printf(\n);}return;
}inline void AG_Insert(ALGraph G, int i, int j) {ArcNode* p (ArcNode*)malloc(sizeof(ArcNode));p-adjvex j;p-nextarc NULL;G.vertices[i].data;ArcNode* head G.vertices[i].firstarc;ArcNode* tail G.vertices[i].firstarc-nextarc;if (tail NULL) {G.vertices[i].firstarc-nextarc p;}else {while (tail ! NULL) {if (tail-adjvex p-adjvex) {p-nextarc tail;head-nextarc p;break;}else {head head-nextarc;tail tail-nextarc;continue;}}if (tail NULL)head-nextarc p;}ArcNode* q (ArcNode*)malloc(sizeof(ArcNode));q-adjvex i;q-nextarc NULL;G.vertices[j].data;head G.vertices[j].firstarc;tail G.vertices[j].firstarc-nextarc;if (tail NULL) {G.vertices[j].firstarc-nextarc q;}else {while (tail ! NULL) {if (tail-adjvex q-adjvex) {q-nextarc tail;head-nextarc q;break;}else {head head-nextarc;tail tail-nextarc;continue;}}if (tail NULL)head-nextarc q;}return;
}inline void AG_Print(ALGraph G) {for (int i 1; i vexnum; i) {if (!G.vertices[i].data) {printf(0\n);continue;}printf(%d , G.vertices[i].data);ArcList Arc G.vertices[i].firstarc-nextarc;while (Arc ! NULL) {printf(%d, Arc-adjvex);Arc Arc-nextarc;if (Arc ! NULL)printf( );}printf(\n);}return;
}int main() {ALGraph Ag;int i, j;scanf(%d %d, vexnum, arcnum);Init(Ag);for (int k 1; k arcnum; k) {scanf(%d %d, i, j);MG_Insert(i, j);AG_Insert(Ag, i, j);}MG_Print();AG_Print(Ag);return 0;
}反复修改调试后都没能解决这题甚至我自己造了几个数据还是不行明明输出看起来没有任何问题也许是 s c a n f scanf scanf和 p r i n t f printf printf的问题吧以前打 O I OI OI的时候也经常遇到各种玄学问题。其实结构体定义里就出了问题 总之之后我就急了直接花不到十分钟打了个暴力程序然后 A C AC AC。思路很简单用bool类型存邻接矩阵输出的时候直接遍历就完事了。输出邻接表时多遍历一次统计信息即可。 男人哈哈哈什么罐头我说曼巴出去。 以下是100pts的代码
//AC
#define _CRT_SECURE_NO_WARNINGS 1
#includecstdio
#includecstring
#includeiostream
using namespace std;int n, m;
bool g[1001][1001];int main() {memset(g, false, sizeof(g));cin n m;int u, v;for (int i 1; i m; i) {cin u v;g[u][v] true, g[v][u] true;}for (int i 1; i n; i) {for (int j 1; j n; j) {if (g[i][j])cout 1;else cout 0;if (j ! n)cout ;}cout endl;}for (int i 1; i n; i) {int ans 0;for (int j 1; j n; j)if (g[i][j])ans;if (!ans)cout ans;else {cout ans ;for (int j 1; j n; j)if (g[i][j])cout j ;}cout endl;}return 0;
}但是
我凌晨写日记复盘今天的时候突然想到了这题要怎么改。首先把所有的 s c a n f scanf scanf和 p r i n t f printf printf换回了 c i n cin cin和 c o u t cout cout的输入输出流然后再通读了一下代码发现一个致命错误——
typedef struct VNode {VertexType data;//问题行ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];我怎么也没想到是结构体里面出了问题本题中我使用了顶点结点的 d a t a data data域记录每个顶点的度但是偷懒直接用了自己之前写的模板导致 d a t a data data的数据类型实际上是 c h a r char char而非 i n t int int属实是低级错误了。所以能过三个点真的是运气好吧。警钟撅烂 改完代码后再对代码整体进行了一点优化提交一遍 A C AC AC完美。 以下是100pts的代码无需开启 O 2 O2 O2加速
//AC 100pts
#define _CRT_SECURE_NO_WARNINGS 1
#includecmath
#includecstdio
#includecstdlib
#includecstring
#includeiostream
#includealgorithm
using namespace std;#define MaxVertexNum 1007
#define MaxMGSize 500007/*
typedef char VertexType;
typedef int EdgeType;
typedef struct {VertexType Vex[MaxVertexNum];EdgeType Edge[MaxVertexNum][MaxVertexNum];
}MGraph;
*/typedef struct ArcNode {int adjvex;struct ArcNode* nextarc;
}ArcNode,* ArcList;
typedef struct VNode {int data;//已更正data的数据类型ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {AdjList vertices;
}ALGraph;int vexnum, arcnum;
int MGraph[MaxMGSize] { 0 };inline void Init(ALGraph G) {
// memset(MGraph, 0, sizeof(MGraph));for (int i 1; i vexnum; i) {ArcList h (ArcList)malloc(sizeof(ArcList));h-adjvex 0;h-nextarc NULL;G.vertices[i].data 0;G.vertices[i].firstarc h;}return;
}inline int Get_K(int i, int j) {if (i j)swap(i, j);return i * (i - 1) / 2 j - 1;//对称矩阵压缩存储下三角
}inline void MG_Insert(int i, int j) {if (i j)swap(i, j);MGraph[Get_K(i, j)] 1;return;
}inline void MG_Print() {for (int i 1; i vexnum; i) {for (int j 1; j vexnum; j) {cout MGraph[Get_K(i, j)];if (j ! vexnum)cout ;}cout endl;}return;
}inline void AG_Insert(ALGraph G, int i, int j) {//简化了邻接表的插入函数ArcNode* p (ArcNode*)malloc(sizeof(ArcNode));p-adjvex j;p-nextarc NULL;G.vertices[i].data;ArcNode* head G.vertices[i].firstarc;ArcNode* tail G.vertices[i].firstarc-nextarc;if (tail NULL) {G.vertices[i].firstarc-nextarc p;}else {while (tail ! NULL) {if (tail-adjvex p-adjvex) {p-nextarc tail;head-nextarc p;break;}else {head head-nextarc;tail tail-nextarc;continue;}}if (tail NULL)head-nextarc p;}return;
}inline void AG_Print(ALGraph G) {//改用了更简洁的cincout流for (int i 1; i vexnum; i) {if (!G.vertices[i].data) {cout 0 endl;continue;}cout G.vertices[i].data ;ArcNode* Arc G.vertices[i].firstarc-nextarc;while (Arc ! NULL) {cout Arc-adjvex;Arc Arc-nextarc;if (Arc ! NULL)cout ;}cout endl;}return;
}int main() {ALGraph Ag;int i, j;cin vexnum arcnum;Init(Ag);for (int k 1; k arcnum; k) {cin i j;MG_Insert(i, j);AG_Insert(Ag, i, j);AG_Insert(Ag, j, i);}MG_Print();AG_Print(Ag);return 0;
}但是 我还是不能接受暴力碾压标程虽说直接开 b o o l bool bool也不能算完全暴力吧……
完整代码也可参看我的Github标准模板写法传送门暴力写法传送门 令人感叹暴力代码 A C AC AC标准模板代码 WA也 A C AC AC但是更慢 这就是 O I OI OI的魅力啊大嘘 以上。
