网站大小多少合适,功能多的免费网站建设,珠海中企网站建设公司,如何做电子海报在网站Floyd大家可能第一时间想到的是他求多源最短路的n算法。其实它还有另外两种算法的嘛qwq。写一发总结好了qwq。 一、多源最短路 放段代码跑#xff0c;注意枚举顺序#xff0c;用邻接矩阵存图。本质是一种动规。 复杂度O(n)。 1 for(int k1;kn;k)
2 for(int i1;in…Floyd大家可能第一时间想到的是他求多源最短路的n³算法。其实它还有另外两种算法的嘛qwq。写一发总结好了qwq。 一、多源最短路 放段代码跑注意枚举顺序用邻接矩阵存图。本质是一种动规。 复杂度O(n³)。 1 for(int k1;kn;k)
2 for(int i1;in;i)
3 for(int j1;jn;j)
4 f[i][j]min(f[i][j],f[i][k]f[k][j]); View Code 放个例题跑。 灾后重建 二、传递闭包 在交际网络中给定若干个元素若干个二元关系关系有传递性。传递闭包就是一种“通过传递性推导出尽量多的元素之间关系的问题”求出可确定排名的元素个数。 实现用一个布尔型的邻接矩阵f[i][j]1表示i与j有关系否则则没有关系。 我们每次可以枚举k点来解决那些间接相关的关系处理。 1 for(int k1;kn;k)
2 for(int i1;in;i)
3 for(int j1;jn;j)
4 f[i][j]|f[i][k]f[k][j]; View Code 例题 [USACO08JAN]牛大赛Cow Contest 对于奶牛的编程能力用f[i][j]1表示i比j强之后就是一个裸的传递闭包。跑一遍后n²统计每只牛它与其他牛的关系是否已经确定意思就是说只要有f[i]j]1或f[j][i]1其中一个就行来统计答案。 Code 1 #includecstdio2 #includealgorithm3 4 using namespace std;5 6 int n,m,ans;7 int f[200][200];8 9 int main()
10 {
11 scanf(%d%d,n,m);
12 for(int i1;im;i)
13 {
14 int x0,y0;
15 scanf(%d%d,x,y);
16 f[x][y]1;
17 }
18 for(int k1;kn;k)
19 for(int i1;in;i)
20 for(int j1;jn;j)
21 f[i][j]|f[i][k]f[k][j];
22 for(int i1;in;i)
23 {
24 int j;
25 for(j1;jn;j)
26 {
27 if(ij) continue;
28 if(f[i][j]0f[j][i]0) break;
29 }
30 if(jn) ans;
31 }
32 printf(%d,ans);
33 return 0;
34 } View Code 三、求无向图最小环 例题1 USACO4.1篱笆回路 这道题难在建图图建好以后就是裸的跑floyd找最小环了。 瞎说一句这题竟然有个数组开了1000的空间但是越界了呀qwq Code 1 /*2 ID:cellur_23 TASK:fence64 LANG:C5 */6 #includecstdio7 #includealgorithm8 #includecstring9
10 using namespace std;
11 const int inf0x3f3f3f3f;
12
13 int n,num,ansinf;
14 int dis[300][300],mapp[300][300];
15 struct node{
16 int len;
17 int lcnt,rcnt,lid,rid,id;
18 int l[300],r[300];
19 }edge[300];
20
21 int main()
22 {
23 scanf(%d,n);
24 for(int i1;in;i)
25 {
26 scanf(%d,edge[i].id);
27 int xedge[i].id;
28 scanf(%d,edge[x].len);
29 scanf(%d%d,edge[x].lcnt,edge[x].rcnt);
30 for(int j1;jedge[x].lcnt;j)
31 scanf(%d,edge[x].l[j]);
32 for(int j1;jedge[x].rcnt;j)
33 scanf(%d,edge[x].r[j]);
34 }
35 for(int i1;in;i)
36 {// lid 这条边左端点的点编号
37 // rid 这条边右端点的点编号
38 if(!edge[i].lid) edge[i].lidnum;
39 for(int j1;jedge[i].lcnt;j)
40 {
41 int xedge[i].l[j];
42 bool flag0;
43 for(int k1;kedge[x].lcnt;k)
44 if(edge[x].l[k]i)
45 {
46 flag1;
47 break;
48 }
49 if(flag) edge[x].lidedge[i].lid;
50 else edge[x].ridedge[i].lid;
51 }
52 if(!edge[i].rid) edge[i].ridnum;
53 for(int j1;jedge[i].rcnt;j)
54 {
55 int xedge[i].r[j];
56 bool flag0;
57 for(int k1;kedge[x].lcnt;k)
58 if(edge[x].l[k]i)
59 {
60 flag1;
61 break;
62 }
63 if(flag) edge[x].lidedge[i].rid;
64 else edge[x].ridedge[i].rid;
65 }
66 }
67 memset(mapp,0x3f,sizeof(mapp));
68 memset(dis,0x3f,sizeof(dis));
69 ansdis[2][33];
70 for(int i1;in;i) mapp[i][i]0,dis[i][i]0;
71 for(int i1;in;i)
72 {
73 int lidedge[i].lid;
74 int ridedge[i].rid;
75 int lenedge[i].len;
76 mapp[rid][lid]mapp[lid][rid]len;
77 dis[rid][lid]dis[lid][rid]len;
78 }
79 //floyd找最小环
80 for(int k1;knum;k)
81 {
82 for(int i1;ik;i)
83 for(int ji1;jk;j)
84 ansmin(ans,dis[i][j]mapp[i][k]mapp[k][j]);
85 for(int i1;inum;i)
86 for(int j1;jnum;j)
87 dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);
88 }
89 printf(%d\n,ans);
90 return 0;
91 } View Code 例题2 POJ 1734 Sightseeing Trip 其实是floyd找最小环的板子题但是由于题目要求输出一种合法的方案所以我们只要再开一个vector就行了。 Code 1 #includecstdio2 #includealgorithm3 #includevector4 #includecstring5 6 using namespace std;7 typedef long long ll;8 9 int n,m;
10 int ans0x3f3f3f3f;
11 int dis[200][200],mapp[200][200],pos[200][200];
12 vectorintpath;
13
14 void get_path(int x,int y)
15 {
16 if(pos[x][y]0) return ;
17 get_path(x,pos[x][y]);
18 path.push_back(pos[x][y]);
19 get_path(pos[x][y],y);
20 }
21
22 int main()
23 {
24 scanf(%d%d,n,m);
25 memset(dis,0x3f,sizeof(dis));
26 for(int i1;in;i) dis[i][i]0;
27 for(int i1;im;i)
28 {
29 int x0,y0,z0;
30 scanf(%d%d%d,x,y,z);
31 dis[x][y]dis[y][x]min(dis[x][y],z);
32 }
33 memcpy(mapp,dis,sizeof(dis));
34 for(int k1;kn;k)
35 {
36 for(int i1;ik;i)
37 for(int ji1;jk;j)
38 if((ll)mapp[i][j]dis[j][k]dis[i][k]ans)
39 {
40 ansmapp[i][j]dis[i][k]dis[k][j];
41 path.clear();
42 path.push_back(i);
43 get_path(i,j);
44 path.push_back(j);
45 path.push_back(k);
46 }
47 for(int i1;in;i)
48 for(int j1;jn;j)
49 if(mapp[i][j]mapp[i][k]mapp[k][j])
50 {
51 mapp[i][j]mapp[i][k]mapp[k][j];
52 pos[i][j]k;
53 }
54 }
55 if(ans0x3f3f3f3f)
56 {
57 printf(No solution.);
58 return 0;
59 }
60 for(int i0;ipath.size();i)
61 printf(%d ,path[i]);
62 return 0;
63 } View Code 转载于:https://www.cnblogs.com/nopartyfoucaodong/p/9590907.html
