离散数学实验四
A - 补图
Description
题目给出一个无向图，求该无向图关于完全图的相对补图，并求该补图的最大度和最小度。方便起见，用邻接矩阵表示该无向图。无向图的节点数不少于2并且不超过500.
Input
多组输入，每组输入第一行是无向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。
Output
每组数据，首先输出n行n列表示补图的邻接矩阵。接下来一行两个用空格分隔的整数，分别代表补图的最大度和最小度。
Sample
Input
4
0 0 1 1
0 0 0 1
1 0 0 0
1 1 0 0
Output
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
2 1
参考代码：
#include int main(){int i,j,n,max,min,f,a[501][501];while(scanf("%d",&n)!=EOF){max=0;min=501;for(i=0;imax)max=f;if(f
B - 指定长度路径数
Description
题目给出一个有n个节点的有向图，求该有向图中长度为k的路径条数。方便起见，节点编号为1,2,…,n，用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500.
例如包含两个节点的有向图，图中有两条边1 → 2 ,2 → 1 。
长度为1的路径有两条：1 → 2 和 2 →1 ；
长度为2的路径有两条：1 → 2 → 1和2 → 1 → 2 ；
偷偷告诉你也无妨，其实这个图无论k取值多少 ( k > 0 )，长度为k的路径都是2条。
Input
多组输入，每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。接下来一行是一个整数k.k小于30.
Output
输出一个整数，即为图中长度为k的路径的条数。
Sample
Input
3
0 1 0
0 0 1
0 0 0
2
Output
1
参考代码：
#includeint e[500][500],c[500][500],b[500][500];int main(){int n,i,j,k,sum,p,q;while(scanf("%d",&n)!=EOF){memset(e,0,sizeof(e));memset(c,0,sizeof(c));for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&e[i][j]);c[i][j]=e[i][j];}}scanf("%d",&k);for(p=1;p C - 建图
Description
编程使得程序可以接受一个图的点边作为输入，然后显示出这个图。
Input
多组测试数据，对于每组测试数据，第一行输入正整数n(1 <= n <= 1000)和m，之后m行输入正整数x、y，表示在点x和点y之间存在有向边相连。
Output
对于每组测试数据，输出图的关系矩阵。
Sample
Input
4 5
1 1
2 2
2 4
3 3
4 4
Output
1 0 0 0
0 1 0 1
0 0 1 0
0 0 0 1
参考代码：
#include int main(){int n,m,x,y,i,j,a[1001][1001];while(scanf("%d%d",&n,&m)!=EOF){memset(a,0,sizeof(a));while(m--){scanf("%d%d",&x,&y);a[x][y]=1;}for(i=1;i<=n;i++){for(j=1;j<=n-1;j++){printf("%d ",a[i][j]);}printf("%d\n",a[i][j]);}}return 0;} D - 最小生成树
Description
在一个无向图中，求最小生成树。
Input
多组测试数据，对于每组测试数据，第1行输入正整数n(1 <= n <= 1000)、m，表示n个顶点(编号从1开始)和m条边。之后m行每行输入u（1 <= u <= n）、v(1 <= v <= n)、w(1 <= w <= 100)，表示在顶点u和顶点v之间存在无向边，且权值为w。
Output
对于每组测试数据，若存在最小生成树则输出最小生成树的权值和，若不存在最小生成树则输出-1。
Sample
Input
3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32
Output
16
参考代码：
C++：
#include #include using namespace std;int f[1200];struct node{int u,v,w;}e[120000];int cmp(struct node a,struct node b){return a.w
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！