1040 【图论基础】求连通子图个数 1041 【图论基础】求最小生成树(prim)

《1040 【图论基础】求连通子图个数 1041 【图论基础】求最小生成树(prim)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【图论基础】求连通子图的个数TimeLimit:10000MS MemoryLimit:65536KTotalSubmit:42Accepted:30Description　　求一个无向图中连通子图的个数。Input　　第一行一个数n，表示无向图的顶点的数量（n<=5000），接下来从第2行到第n+1行，每行有n个数（1表示相应点有直接通路，0表示无直接通路），形成一个n*n的矩阵，用以表示这个无向图。示例：Output　　输出一个数，表示这个图含有连通子图的个数。SampleInput51010001110111100111000001Sam

2、pleOutput自己算吧！Source·var·i,j,n,ans,x:longint;·a:array[1..5000,0..5000]oflongint;·b:array[1..5000]ofboolean;·proceduredfs(x:longint);·vari:longint;·begin·b[x]:=false;·fori:=1toa[x,0]doifb[a[x,i]]then·dfs(a[x,i]);·end;··begin·readln(n);·fori:=1tondo·forj:=1tondobegin·read(x);·

3、ifx=1thenbegin·inc(a[i,0]);a[i,a[i,0]]:=j;·end;·end;·fillchar(b,sizeof(b),true);·fori:=1tondoifb[i]thenbegin·inc(ans);·dfs(i);·end;·writeln(ans);·end.【图论基础】求最小生成树（prim）TimeLimit:10000MS MemoryLimit:65536KTotalSubmit:119Accepted:58Description　　求一个图的最小生成树。这个图边较多，但点较少，宜用prim算法。

4、Input　　第一行一个数n，表示无向图的顶点的数量（n<=1000），接下来从第2行到第n+1行，每行有n个数（0表示相应点之间无边直接相连，不为0表示相应点之间有边直接相连，其值即为相连边的权值），形成一个n*n的矩阵，用以表示这个无向图。Output　　一行，仅一个数，表示最小生成树的边权值和。SampleInput80946000090020000400190006210026000900300000230070006000200000720SampleOutput自己算。Source·var·i,j,k,n,min:longint;·

5、a:array[1..1000,1..1000]oflongint;·b:array[1..1000]oflongint;·c:array[1..1000]ofboolean;·begin·readln(n);·fori:=1tondo·forj:=1tondoread(a[i,j]);·fillchar(c,sizeof(c),0);·fillchar(b,sizeof(b),$7);·k:=1;·fori:=1ton-1dobegin·c[k]:=true;·forj:=1tondo·if(a[k,j]<>0)andnotc[j]and(a

6、[k,j]