排列组合以及相关STL总结

#排列组合以及相关STL总结 相关链接 相关文档 next_permutation prev_permutation 相关博客 ACM~排列组合&&hdu例子 ACM学习历程21——各种排列组合问题 有关组合数学的公式 排列公式P(n,r)=n!/r! 组合公式C(n,r)=n!/(r!*(n-r)!) C(n,r)=C(n-1,r)+C(n-1,r-1) 错排公式d[1]=0,d[2]=1 d[n]=(n-1)*(d[n-1]+d[n-2]) 卡特兰数 前几项 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012… 公式C(n)=C(2n,n)/(n+1) STL中的全排列函数 函数声明 : #include<algorithm> bool next_permutation( iterator start, iterator end); next_permutation()函数功能是输出全部比当前排列大的排列。顺序是从小到大 prev_permutation()函数功能是输出全部比当前排列小的排列,顺序是从大到小 复杂度 至多 N/2 次交换,其中 N = std::distance(first, last) 典型实现在排列的整个序列上,平均每次调用使用约 3 次比较和 1.5 次交换 例题 : hdu-1027 用next_permutation()就可以简单的解决 /************************************************************************* > File Name: p.cpp > Author: Wqr_ > Mail: xueduanwei@126.com > Created Time: 2019年05月10日 星期五 10时23分37秒 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<map> #include<queue> #include<cmath> using namespace std; typedef long long ll; int n, m; int num[1010]; int main(){ while(cin >> n >> m){ for(int i = 0; i < n; i++){ num[i] = i + 1; } m--; while(m--){ next_permutation(num, num + n); } for(int i = 0; i < n; i++){ if(i) printf(" "); printf("%d", num[i]); } cout << endl; } return 0; }
 2019-05-10   acm    总结  排列组合 

STL-map 总结

STL-map 总结 文档链接 map基本操作 在STL的头文件中<map>中定义了模版类map和multimap,用有序二叉树表存储类型为pair<const Key, T>的元素对序列. 序列中的元素以 const Key 部分作为标识, map 中所有元素的Key值必须是唯一的,multimap 则允许有重复的 Key 值. 可以将map看作是由Key标识元素的元素集合,这类容器也被称为“关联容器”,可以通过一个Key值来快速决定一个元素,因此非常适合于需要按照Key值查找元素的容器. map模版类需要四个模版参数,第一个是键值类型,第二个是元素类型,第三个是比较算子,第四个是分配器类型。其中键值类型和元素类型是必要的. 定义map对象的代码示例: map<string, int> m; 基本操作 /* 向map中插入元素 */ // [key]操作是map很有特色的操作,如果在map中存在键值为key的元素对, 则返回该元素对的值域部分,否则将会创建一个键值为key的元素对,值域为默认值。所以可以用该操作向map中插入元素对或修改已经存在的元素对的值域部分. m[key] = value; m.insert(make_pair(key, value)); // 也可以直接调用insert方法插入元素对,insert操作会返回一个pair,当map中没有与key相匹配的键值时,其first是指向插入元素对的迭代器,其second为true;若map中已经存在与key相等的键值时,其first是指向该元素对的迭代器,second为false。 /* 查找元素 */ // 要注意的是,当与该键值相匹配的元素对不存在时,会创建键值为key(当另一个元素是整形时,m[key]=0)的元素对. int i = m[key]; // 如果map中存在与key相匹配的键值时,find操作将返回指向该元素对的迭代器,否则,返回的迭代器等于map的end()(参见vector中提到的begin()和end()操作). map<string, int>::iterator it = m.find(key); /* 删除元素 */ // 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数. m.erase(key); // 删除由迭代器it所指定的元素对,并返回指向下一个元素对的迭代器. m.erase(it); /* 其他操作 */ m.size(); // 返回元素个数 m.empty(); // 判断是否为空 m.clear(); // 清空所有元素 map的排序 为了实现快速查找, map内部本身就是按序存储的(比如红黑树). 在我们插入<key, value>键值对时, 就会按照key的大小顺序进行存储, 这也是作为key的类型必须能够进行<运算比较的原因. 但有些时候需要用特殊的规则进行排序, 这时可以用vector进行间接地排序 map中通过pair储存数据, 所以定义 map<key, value> m; typedef pair<key, value> pa; //把m中的值复制到vec中 vector<pa> vec(m.begin(), m.end()); 之后定义排序函数通过vector排序 例题hdu-1236 /************************************************************************* > File Name: c.cpp > Author: Wqr_ > Mail: xueduanwei@126.com > Created Time: 2019年05月06日 星期一 19时40分20秒 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<map> #include<queue> #include<cmath> using namespace std; typedef pair<string, int> pa; int fen[20]; //定义比较函数 bool cmp(const pa &a, const pa &b){ if(a.second != b.second) return a.second > b.second; else{ return a.first.compare(b.first) < 0 ? 1 : 0; } } int main(){ int n, m, g; while(scanf("%d", &n) && n){ scanf("%d %d", &m, &g); int ans = 0; map<string, int> jifen; for(int i = 0; i < m; i++){ scanf("%d", fen + i + 1); } for(int i = 0; i < n; i++){ string hao; int num; cin >> hao >> num; jifen[hao] = 0; for(int j = 0; j < num; j++){ int in; scanf("%d", &in); jifen[hao] += fen[in]; } if(jifen[hao] >= g){ ans++; } } cout << ans << endl; vector<pa> vec(jifen.begin(), jifen.end()); // 排序 sort(vec.begin(), vec.end(), cmp); for(pa vecc : vec){ if(vecc.second >= g) cout << vecc.first << " " << vecc.second << endl; } } return 0; }
 2019-05-08   acm    总结  map 

poj-1182 带权并查集

link 带权并查集做法 (向量) 参考博文 带权并查集与普通并查集的区别主要在find()和uni()上 在进行两项操作的同时要对节点的权值进行更新, 参考参考博文的做法, 使用了类似向量的思想 变量解释 node中 per父节点 rel与父节点(即向量指向的节点)的关系 0=>同类 1=>被父节点吃 2=>吃父节点 high高度, 本题中没有 (至少我的码里没用…) 合并 -假设有 pa, a, pb, b 四个节点, a 与 b 有关系, 具体如图 将 pb 连接到 pa 时侯, 就可以很容易的得到 pa 与 pb 的关系 b->pb + pb->pa = b->a + a->pa 推出pb->pa = b->a + a->pa - b->pb 转化为代码 node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3; find() (同时压缩路径) 假设有 a, b, c 三个节点, 关系如图 将 c 连接到 a 时 c->a = c->b + b->a 转化为代码node[a].rel = (node[a].rel + node[tmp].rel + 3) % 3; 通过 tmp 进行递归迭代进行路径压缩 code /********************************************************** > File Name : poj-1182-jq.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 22 09:57:18 **********************************************************/ // 282ms #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> using namespace std; struct nodep{ int per; int high; //0=>同类 1=>被父节点吃 2=>吃父节点 int rel; }node[50100]; int n, k; int D[100010]; int X[100010]; int Y[100010]; void init(){ for(int i = 0 ; i < n; i++){ node[i].per = i; node[i].rel = 0; } } int find(int a){ if(node[a].per == a) return a; else{ int tmp = node[a].per; node[a].per = find(node[a].per); node[a].rel = (node[a].rel + node[tmp].rel + 3) % 3; return node[a].per; } } void uni(int a, int b, int d){ int pa = find(a); int pb = find(b); if(pa == pb) return ; /* if(node[pa].high > node[pb].high){ node[pb].per = pa; node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3; }else if(node[a].high < node[b].high){ node[a].per = b; node[pa].rel = (d + node[b].rel - node[a].rel + 3) % 3; }else{ node[a].per = b; node[pa].rel = (d + node[b].rel - node[a].rel + 3) % 3; node[pb].high++; } 合并树 注意:被 a 吃,所以以 a 的根为父 也就是说, 不能按照白书上介绍的那样进行压缩操作 */ node[pb].per = pa; node[pb].rel = (d + node[a].rel - node[b].rel + 3) % 3; } bool same(int a, int b){ return find(a) == find(b); } int getrel(int a, int b){ // 所求为 a => b 的关系 find(a); find(b); return (node[a].rel - node[b].rel + 3) % 3; } void solve(){ init(); int ans = 0; for(int i = 0; i < k; i++){ int d = D[i]; int x = X[i] - 1; int y = Y[i] - 1; if(d == 2 && x == y){ ans++; continue; } if(x < 0 || x >= n || y < 0 || y >= n){ ans++; continue; } if(same(x, y)){ if(d == 1 && getrel(x, y) != 0) ans++; if(d == 2 && getrel(x, y) != 2) ans++; } uni(x, y, d - 1); } printf("%d", ans); } int main(){ cin >> n >> k; for(int i = 0; i < k; i++){ scanf("%d %d %d", D + i, X + i, Y + i); } solve(); return 0; } 白书做法 (分类) /********************************************************** > File Name : poj-2236.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 20 21:09:04 **********************************************************/ // 329ms #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <string> using namespace std; int par[150010]; int high[150010]; int D[100010]; int X[100010]; int Y[100010]; int n, k; void init(int n){ for(int i = 0; i < n; i++){ par[i] = i; high[i] = 0; } } int find(int a){ if(par[a] == a) return a; else{ return par[a] = find(par[a]); } } void unite(int a, int b){ a = find(a); b = find(b); if(a == b) return ; if(high[a] > high[b]){ par[b] = a; }else if(high[a] < high[b]){ par[a] = b; }else{ par[a] = b; high[b]++; } } bool same(int a, int b){ return find(a) == find(b); } void solve(){ init(n * 3); int ans = 0; for(int j = 0; j < k; j++){ int d = D[j]; int x = X[j] - 1; int y = Y[j] - 1; if(x < 0 || x >= n || y < 0 || y >= n){ ans++; continue; } if(d == 1){ if(same(x, y + n) || same(x, y + 2 * n)){ ans++; }else{ unite(x, y); unite(x + n, y + n); unite(x + 2 * n, y + 2 * n); } } if(d == 2){ if(same(x, y) || same(x, y + 2 * n)){ ans++; }else{ unite(x, y + n); unite(x + n, y + 2 * n); unite(x + 2 * n, y); } } } cout << ans << endl; } int main(){ cin >> n >> k; int din, xin, yin; for(int i = 0; i < k; i++){ scanf("%d %d %d", D + i, X + i, Y + i); } solve(); return 0; }
 2019-03-28   acm    并查集 

poj-1860 poj-3295 Bellman-Ford判断负权回路

poj-1860 link 题目大意 有多个兑换点, 每个兑换点可以兑换两种货币. 假设本来有的货币种类为s, 问能否通过不断兑换最终回到s并且使总金增加 理解 如果存在正权回路则说明可以钱无限增加, 找到正权回路直接输出YES就行了, 否则输出NO code /********************************************************** > File Name : poj-1860.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 24 15:43:13 **********************************************************/ #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> using namespace std; struct poin{ int a, b; double r, c; }expp[220]; // 刚开始定义的是exp[220], 不知道这是个关键字, 报错了 int nume; int n, m, s; double v; // 到第[]种货币的最大值 double dis[101]; bool bell(){ memset(dis, 0, sizeof(dis)); dis[s] = v; for(int i = 0; i < n - 1; i++){ bool flag = false; for(int j = 0; j < nume; j++){ if(dis[expp[j].b] < (dis[expp[j].a] - expp[j].c) * expp[j].r){ dis[expp[j].b] = (dis[expp[j].a] - expp[j].c) * expp[j].r; flag = true; } } if(!flag) break; } for (int j = 0; j < nume; j++) { if (dis[expp[j].b] < (dis[expp[j].a] - expp[j].c) * expp[j].r) { return true; } } return false; } int main(){ while(cin >> n >> m >> s >> v){ nume = 0; int exa, exb; double exra, exca, exrb, excb; for(int i = 0; i < m; i++){ scanf("%d %d %lf %lf %lf %lf", &exa, &exb, &exra, &exca, &exrb, &excb); expp[nume].a = exa; expp[nume].b = exb; expp[nume].r = exra; expp[nume++].c = exca; expp[nume].a = exb; expp[nume].b = exa; expp[nume].r = exrb; expp[nume++].c = excb; } if(bell()) printf("YES\n"); else printf("NO\n"); } return 0; } poj-3295 link 题目大意 有f个农场, 每个农场有n个点m条路, 有w个虫洞, 问针对每个农场能否看到以前的自己 理解 判断是否有负权回路, 有就可以 code /********************************************************** > File Name : poj-3295.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 24 17:15:01 **********************************************************/ #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> #define INF 1<<28 using namespace std; int n, m, w; int eee; struct edge{ int a, b, cost; }es[10010]; int dis[10010]; bool bell(){ fill(dis, dis + n, INF); dis[1] = 0; for(int i = 0; i < n - 1; i++){ bool flag = false; for(int j = 0; j < eee; j++){ if(dis[es[j].b] > dis[es[j].a] + es[j].cost){ dis[es[j].b] = dis[es[j].a] + es[j].cost; flag = true; } } if(!flag) break; } for (int j = 0; j < eee; j++) { if (dis[es[j].b] > dis[es[j].a] + es[j].cost) { return true; } } return false; } int main(){ int f; cin >> f; while(f--){ eee = 0; cin >> n >> m >> w; int a, b, c; for(int i = 0; i < m; i++){ scanf("%d %d %d", &a, &b, &c); es[eee].a = a; es[eee].b = b; es[eee++].cost = c; es[eee].a = b; es[eee].b = a; es[eee++].cost = c; } for(int i = 0; i < w; i++){ scanf("%d %d %d", &a, &b, &c); es[eee].a = a; es[eee].b = b; es[eee++].cost = -c; } if(bell()) printf("YES\n"); else printf("NO\n"); } return 0; }
 2019-03-28   acm    最短路 

手机端 Termux linux vim c++ 环境的配置

前言 完成效果图 本文在Termux 高级终端安装使用配置教程的基础上进行vim的更深一步配置 感谢大佬的教程 1. gcc的安装 输入pkg install clang 这个我不确定对不对了,如果出了错误请按照如下操作 输入gcc 会弹出一些信息,其中有一个pkg install *** 输入就可以了 2. vimrc的配置 输入命令vim ~/.vimrc 在vimrc中添加如下代码 nmap <c-c> :w! ~/storage/shared/copy.txt set tabstop=4 set softtabstop=4 set shiftwidth=4 set autoindent set cindent set smarttab :set ts=4 :set expandtab :%retab! syntax on set laststatus=0 set number filetype on set showcmd if version >= 603 set helplang=cn set encoding=utf-8 endif autocmd BufNewFile *.cpp,*.[ch],*.sh,*.java exec ":call SetTitle()" func SetTitle() if &filetype == 'sh' call setline(1,"\#########################################################################") call append(line("."), "\# File Name: ".expand("%")) call append(line(".")+1, "\# Author: Wqr_") call append(line(".")+2, "\# mail: xueduanwei@126.com") call append(line(".")+3, "\# Created Time: ".strftime("%c")) call append(line(".")+4, "\#########################################################################") call append(line(".")+5, "\#!/bin/bash") call append(line(".")+6, "") else call setline(1, "/*************************************************************************") call append(line("."), " > File Name: ".expand("%")) call append(line(".")+1, " > Author: Wqr_") call append(line(".")+2, " > Mail: xueduanwei@126.com ") call append(line(".")+3, " > Created Time: ".strftime("%c")) call append(line(".")+4, " ************************************************************************/") call append(line(".")+5, "") endif if &filetype == 'cpp' call append(line(".")+6, "#include<iostream>") call append(line(".")+7, "#include<cstdio>") call append(line(".")+8, "#include<cstring>") call append(line(".")+9, "#include<string>") call append(line(".")+10, "#include<vector>") call append(line(".")+11, "#include<algorithm>") call append(line(".")+12, "using namespace std;") call append(line(".")+13, "") endif if &filetype == 'c' call append(line(".")+6, "#include<stdio.h>") call append(line(".")+7, "") endif autocmd BufNewFile * normal G endfunc map <c-g> :call CompileRunGcc()<CR> func! CompileRunGcc() exec "w" if &filetype == 'c' exec "!g++ % -o %<" exec "! ./%<" elseif &filetype == 'cpp' exec "!g++ % -o %<" exec "! ./%<" elseif &filetype == 'java' exec "!javac %" exec "!java %<" elseif &filetype == 'sh' :!./% endif endfunc map <c-d> :call Rungdb()<CR> func! Rungdb() exec "w" exec "!g++ % -g -o %<" exec "!gdb ./%<" endfunc autocmd FileType c,cpp map <buffer> <leader><space> :w<cr>:make<cr> set completeopt=preview,menu "允许插件 filetype plugin on "共享剪贴板 set clipboard+=unnamed set autowrite set enc=utf-8 set fencs=utf-8,ucs-bom,shift-jis,gb18030,gbk,gb2312,cp936 "语言设置 set langmenu=zh_CN.UTF-8 set helplang=cn filetype plugin on filetype indent on set iskeyword+=_,$,@,%,#,- :inoremap ( ()<ESC>i :inoremap ) <c-r>=ClosePair(')')<CR> :inoremap { {<CR>}<ESC>O :inoremap } <c-r>=ClosePair('}')<CR> :inoremap [ []<ESC>i :inoremap ] <c-r>=ClosePair(']')<CR> :inoremap " ""<ESC>i :inoremap ' ''<ESC>i function! ClosePair(char) if getline('.')[col('.') - 1] == a:char return "\<Right>" else return a:char endif endfunction filetype plugin indent on "打开文件类型检测, 加了这句才可以用智能补全 set completeopt=longest,menu 解释 我在根目录下创建了一个名为copy.txt的文件,用来作为系统间复制的桥梁,这个copy.txt需要手动进行创建 <c-c>代表ctrl + c 以此类推 在此操作后会执行命令:w! ~/storage/shared/copy.txt将文件保存到copy.txt中 需要注意的是,执行此操作需要文件有相应的权限,使用chmod指令操作,由于条件比较复杂,具体请自行百度 ctrl + g可以启用gcc进行编译,ctrl + d可以启用gdb进行调试 预添加了头文件和一些信息,可以按需求修改 3. 插件的安装(可跳过) 1. 安装vundle link 首先cd ~/.vim如果没有此文件夹则使用mkdir创建一个 在.vim文件夹中创建文件夹bundlemkdir bundle 执行git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim 可能没有git 按提示操作即可 在.vimrc中前添加如下代码 set nocompatible " be iMproved, required filetype off " required " set the runtime path to include Vundle and initialize set rtp+=~/.vim/bundle/Vundle.vim call vundle#begin() " alternatively, pass a path where Vundle should install plugins "call vundle#begin('~/some/path/here') " let Vundle manage Vundle, required Plugin 'VundleVim/Vundle.vim' " The following are examples of different formats supported. " Keep Plugin commands between vundle#begin/end. " plugin on GitHub repo Plugin 'tpope/vim-fugitive' " plugin from http://vim-scripts.org/vim/scripts.html " Plugin 'L9' " Git plugin not hosted on GitHub Plugin 'git://git.wincent.com/command-t.git' " git repos on your local machine (i.e. when working on your own plugin) Plugin 'file:///home/gmarik/path/to/plugin' " The sparkup vim script is in a subdirectory of this repo called vim. " Pass the path to set the runtimepath properly. Plugin 'rstacruz/sparkup', {'rtp': 'vim/'} " Install L9 and avoid a Naming conflict if you've already installed a " different version somewhere else. " Plugin 'ascenator/L9', {'name': 'newL9'} " All of your Plugins must be added before the following line call vundle#end() " required filetype plugin indent on " required " To ignore plugin indent changes, instead use: "filetype plugin on " " Brief help " :PluginList - lists configured plugins " :PluginInstall - installs plugins; append `!` to update or just :PluginUpdate " :PluginSearch foo - searches for foo; append `!` to refresh local cache " :PluginClean - confirms removal of unused plugins; append `!` to auto-approve removal " " see :h vundle for more details or wiki for FAQ " Put your non-Plugin stuff after this line 2. 安装缩进可视化插件 link 将文件下载并解压到~/.vim/bundle/目录下 在前面刚添加的代码块中添加Plugin 'Yggdroot/indentLine' 在前面添加的代码块后添加let g:indentLine_color_term = 239
 2019-03-28   环境    linux  Termux  android 

蚁群算法解决tsp以及不闭合tsp问题

前言 思路来源, 这篇文章里介绍的真的是非常详细, 文章中有大连理工大学的pdf, 也可也学到很多 蚁群算法属于智能算法, 并不一定收敛到最优解, 但对75点一下规模的问题能很好的解决 代码参考 思路 tsp问题的思路在前言中的文章里已经有了详细的介绍, 所以只介绍我解决不闭合tsp问题的思路 tsp问题的解决 原理见前言文章与code, 仅展示下结果和逻辑图 30个点感觉并不是很好 50点 不闭合tsp问题的解决 与tsp问题类似, 但主要差别只遍历所有的点但不返回原点. 第一阶段 在随机的城市生成蚂蚁, 蚂蚁的总数量与城市数量相等 每一只蚂蚁通过由信息素与能见度共同决定的规则产生前往不同城市的概率, 并以这个概率随机决定下一个城市 所有蚂蚁回到原点后更新每条路径上的信息素含量 达到遍历次数后进入第二阶段 第二阶段 在随机的城市生成SUPER蚂蚁, SUPER蚂蚁的总数量与城市数量相等 每一只SUPER蚂蚁通过由信息素与能见度共同决定的规则产生前往不同城市的概率, 并以这个概率随机决定下一个城市 所有SUPER蚂蚁遍历过除了不闭合tsp问题的起点外的所有的点前往不闭合tsp问题的起点 计算并不断更新最短路径的SUPER蚂蚁 达到迭代次数后输出最短路径的SUPER蚂蚁 与简单贪心的比较 30 点 50 点 code /************************************************************************* > File Name: YiQun_Tsp.cpp > Author: Wqr_ > Mail: xueduanwei@126.com > Created Time: Sun Oct 14 22:56:12 2018 ************************************************************************/ // 这个是返回的 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<vector> #include<algorithm> #include<cmath> using namespace std; #define random(x)(rand()%x) const int NUM = 30; // 城市的数量以及蚂蚁的数量 const int ANT_NUM = NUM; // 蚂蚁的数量 const int CITY_NUM = NUM; // 城市 double dis[NUM][NUM]; double info[NUM][NUM]; const double mmax = 1 << 21; double tanXindis; #define TNUM 2000 #define ALPHA 1 #define BETA 4 //返回指定范围内的随机整数 int rnd(int nLow, int nUpper) { return nLow + (nUpper - nLow)*rand() / (RAND_MAX + 1); } //返回指定范围内的随机浮点数 double rnd(double dbLow, double dbUpper) { double dbTemp = rand() / ((double)RAND_MAX + 1.0); return dbLow + dbTemp * (dbUpper - dbLow); } // 蚁群的语句 struct Ant { int Path[CITY_NUM]; //路径顺序 double length; //路径长度 int visit[CITY_NUM]; //记录城市是否被访问过 int now; //当前城市 int visitNo; //第几个城市 //初始化 void Init() { memset(visit, 0, sizeof(visit)); length = 0; now = rnd(0, CITY_NUM);//随机选择一个出发城市 Path[0] = now; visit[now] = 1; visitNo = 1; } //选择下一个城市 int chooseNextCity() { int next = -1; //下一个城市的编号 //计算当前城市和没去过的城市之间的信息素总和 double dbTotal = 0.0; double gaiLv[CITY_NUM]; //各个城市被选中的概率 for (int i = 0; i < CITY_NUM; i++) { if (!visit[i]) { gaiLv[i] = pow(info[now][i], ALPHA) *pow(1.0 / dis[now][i], BETA); dbTotal += gaiLv[i]; } else { gaiLv[i] = 0; } } //进行轮盘赌博 (随缘 double dbTemp = 0.0; if (dbTotal > 0.0) { dbTemp = rnd(0.0, dbTotal); for (int i = 0; i < CITY_NUM; i++) { if (!visit[i]) { dbTemp -= gaiLv[i]; if (dbTemp < 0.0) { next = i; break; } } } } // 如果信息素含量很小, 就选出现的第一个 if (next == -1) { for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) { next = i; break; } } } return next; } void Move() { int next = chooseNextCity(); Path[visitNo] = next; visit[next] = 1; now = next; // 计算新的距离 length += dis[Path[visitNo - 1]][Path[visitNo]]; visitNo++; } // 搜索 void Search() { Init(); // 经过所有城市 while (visitNo < CITY_NUM) { Move(); } // 回到起始点 length += dis[Path[CITY_NUM - 1]][Path[0]]; } }; struct TSP { Ant ants[ANT_NUM]; //一群蚂蚁 Ant bestAnt; // 路径最短的蚂蚁 void Init() { //初始化环境信息素 for (int i = 0; i < CITY_NUM; i++) { for (int j = 0; j < CITY_NUM; j++) { info[i][j] = ANT_NUM * 15 / tanXindis; } } } void Updateinfo() { double tmpinfo[CITY_NUM][CITY_NUM]; memset(tmpinfo, 0, sizeof(tmpinfo)); int m = 0; int n = 0; //遍历每只蚂蚁 for (int i = 0; i < ANT_NUM; i++) { for (int j = 1; j < CITY_NUM; j++) { m = ants[i].Path[j]; n = ants[i].Path[j - 1]; tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length; tmpinfo[m][n] = tmpinfo[n][m]; } //最后城市和开始城市之间的信息素 n = ants[i].Path[0]; tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length; tmpinfo[m][n] = tmpinfo[n][m]; } //更新环境信息素 for (int i = 0; i < CITY_NUM; i++) { for (int j = 0; j < CITY_NUM; j++) { //最新的环境信息素 = 留存的信息素 + 新留下的信息素 info[i][j] = info[i][j] * 0.5 + tmpinfo[i][j]; } } } //寻找路径,迭代TNUM次 void Search() { bestAnt.length = 1 << 21; for (int i = 0; i < TNUM; i++) { for (int j = 0; j < ANT_NUM; j++) { ants[j].Search(); } for (int j = 0; j < ANT_NUM; j++) { if (bestAnt.length > ants[j].length) { bestAnt = ants[j]; } } Updateinfo(); } for (int i = 0; i < CITY_NUM; i++) { if (i) cout << "->"; cout << bestAnt.Path[i]; } cout << "->" << bestAnt.Path[0]; cout << endl; cout << "距离为 : "; cout << bestAnt.length << endl; } }; // 贪心法的语句 double TanXin(int from, int* visit, double sum, int* shunXv, int pointNum) { int flag = true; for (int i = 0; i < NUM; i++) { if (visit[i] == 0) { flag = false; break; } } if (flag) return sum; double min = 1000000; int to; for (int i = 0; i < NUM; i++) { if (dis[from][i] < min && visit[i] == 0) { min = dis[from][i]; to = i; } } sum += dis[from][to]; visit[to] = 1; shunXv[pointNum++] = to; return TanXin(to, visit, sum, shunXv, pointNum); } double qiujv(int x1, int y1, int x2, int y2) { return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2)); } struct point { int x; int y; }; // 主函数 int main() { // fanWei 代表范围 // chuShi 代表起始位置, 即0 int fanWei; int chuShi = 0; cout << "请输入范围 : "; cin >> fanWei; point point[NUM]; for (int i = 0; i < NUM; i++) { point[i].x = random(fanWei); point[i].y = random(fanWei); } for (int i = 0; i < NUM; i++) { for (int j = 0; j < NUM; j++) { dis[i][j] = qiujv(point[i].x, point[i].y, point[j].x, point[j].y); } } double min = 100000; // 最小值 int to; //要去的 double sum = 0; //总数 int shunXv[NUM] = { 0 }; // 顺序 int visit[NUM] = { 0 }; // 储存访问过的点 for (int i = 1; i < NUM; i++) { if (dis[0][i] < min) { min = dis[0][i]; to = i; } } sum += dis[0][to]; shunXv[1] = to; visit[0] = 1; visit[to] = 1; tanXindis = TanXin(to, visit, sum, shunXv, 2); tanXindis += dis[shunXv[49]][0]; cout << endl; cout << "*********** 贪心的结果 **********" << endl; for (int i = 0; i < NUM; i++) { if (i) cout << "->"; cout << shunXv[i]; } cout << "->" << 0; cout << endl; cout << "距离为 : " << tanXindis << endl; cout << endl; cout << "*********** 蚁群的结果 **********" << endl; TSP tsp; tsp.Init(); tsp.Search(); return 0; } /************************************************************************* > File Name: YiQun.cpp > Author: Wqr_ > Mail: xueduanwei@126.com > Created Time: Sun Oct 14 22:56:12 2018 ************************************************************************/ // 这个是不返回起点的 #include"pch.h" #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<vector> #include<algorithm> #include<cmath> using namespace std; #define random(x)(rand()%x) const int NUM = 30; // 城市的数量以及蚂蚁的数量 const int ANT_NUM = NUM; // 蚂蚁的数量 const int CITY_NUM = NUM; // 城市 double dis[NUM][NUM]; double info[NUM][NUM]; const double mmax = 1 << 21; double tanXindis; #define TNUM 2000 #define ALPHA 1 #define BETA 4 //返回指定范围内的随机整数 int rnd(int nLow, int nUpper) { return nLow + (nUpper - nLow)*rand() / (RAND_MAX + 1); } //返回指定范围内的随机浮点数 double rnd(double dbLow, double dbUpper) { double dbTemp = rand() / ((double)RAND_MAX + 1.0); return dbLow + dbTemp * (dbUpper - dbLow); } // 蚁群的语句 struct Ant { int Path[CITY_NUM]; //路径顺序 double length; //路径长度 int visit[CITY_NUM]; //记录城市是否被访问过 int now; //当前城市 int visitNo; //第几个城市 //初始化 void Init() { memset(visit, 0, sizeof(visit)); length = 0; now = rnd(1, CITY_NUM);//随机选择一个除0的城市出发城市 Path[0] = now; visit[now] = 1; visitNo = 1; } //选择下一个城市 int chooseNextCity() { int next = -1; //下一个城市的编号 //计算当前城市和没去过的城市之间的信息素总和 double dbTotal = 0.0; double gaiLv[CITY_NUM]; //各个城市被选中的概率 // 因为0点作为起点, 所以不计入循环 for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) { gaiLv[i] = pow(info[now][i], ALPHA) *pow(1.0 / dis[now][i], BETA); dbTotal += gaiLv[i]; } else { gaiLv[i] = 0; } } //进行轮盘赌博 (随缘 double dbTemp = 0.0; if (dbTotal > 0.0) { dbTemp = rnd(0.0, dbTotal); // 因为0点作为起点, 所以不计入循环 for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) { dbTemp -= gaiLv[i]; if (dbTemp < 0.0) { next = i; break; } } } } // 如果信息素含量很小, 就选出现的第一个 if (next == -1) { for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) { next = i; break; } } } return next; } void Move() { int next = chooseNextCity(); Path[visitNo] = next; visit[next] = 1; now = next; // 计算新的距离 length += dis[Path[visitNo - 1]][Path[visitNo]]; visitNo++; } // 搜索 void Search() { Init(); // 经过除去零点的所有城市 while (visitNo < CITY_NUM - 1) { Move(); } // 回到0点 Path[CITY_NUM - 1] = 0; visit[0] = 1; length += dis[Path[CITY_NUM - 1 - 1]][Path[CITY_NUM - 1]]; } }; // 从零点出发的超级蚂蚁 struct SuperAnt { int Path[CITY_NUM]; //路径顺序 double length; //路径长度 int visit[CITY_NUM]; //记录城市是否被访问过 int now; //当前城市 int visitNo; //第几个城市 //初始化 void Init() { memset(visit, 0, sizeof(visit)); length = 0; now = 0; // 以0为起始城市 Path[0] = now; visit[now] = 1; visitNo = 1; } int chooseNextCity() { int next = -1; double dbTotal = 0.0; double gaiLv[CITY_NUM]; // 因为 0 已经被选中 , 不再重复选择 for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) { gaiLv[i] = pow(info[now][i], ALPHA) *pow(1.0 / dis[now][i], BETA); dbTotal += gaiLv[i]; } else { gaiLv[i] = 0; } } //进行轮盘赌博 (随缘 double dbTemp = 0.0; if (dbTotal > 0.0) { dbTemp = rnd(0.0, dbTotal); // 因为 0 已经被选中 , 不再重复选择 for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) { dbTemp -= gaiLv[i]; if (dbTemp < 0.0) { next = i; break; } } } } if (next == -1) { for (int i = 1; i < CITY_NUM; i++) { if (!visit[i]) //城市没去过 { next = i; break; } } } return next; } void Move() { int next = chooseNextCity(); Path[visitNo] = next; visit[next] = 1; now = next; length += dis[Path[visitNo - 1]][Path[visitNo]]; visitNo++; } //搜索 void Search() { Init(); // 让超级蚂蚁经过所有城市 while (visitNo < CITY_NUM) { Move(); } } }; struct TSP { Ant ants[ANT_NUM]; //一群蚂蚁 SuperAnt SuperAnts[ANT_NUM]; //一群超级蚂蚁 SuperAnt bestSuperAnt; // 路径最短的超级蚂蚁 void Init() { //初始化环境信息素 for (int i = 0; i < CITY_NUM; i++) { for (int j = 0; j < CITY_NUM; j++) { info[i][j] = ANT_NUM * 15 / tanXindis; } } } void Updateinfo() { //puts("update info"); double tmpinfo[CITY_NUM][CITY_NUM]; memset(tmpinfo, 0, sizeof(tmpinfo)); int m = 0; int n = 0; //遍历每只蚂蚁 for (int i = 0; i < ANT_NUM; i++) { //puts(""); for (int j = 1; j < CITY_NUM; j++) { m = ants[i].Path[j]; n = ants[i].Path[j - 1]; //printf("%d %d\n", m, n); tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length; tmpinfo[m][n] = tmpinfo[n][m]; } //最后城市和开始城市之间的信息素 n = ants[i].Path[0]; tmpinfo[n][m] = tmpinfo[n][m] + 3 * ANT_NUM / ants[i].length; tmpinfo[m][n] = tmpinfo[n][m]; } //更新环境信息素 for (int i = 0; i < CITY_NUM; i++) { for (int j = 0; j < CITY_NUM; j++) { //最新的环境信息素 = 留存的信息素 + 新留下的信息素 info[i][j] = info[i][j] * 0.5 + tmpinfo[i][j]; } } } //寻找路径,迭代TMAC次 void Search() { for (int i = 0; i < TNUM; i++) { for (int j = 0; j < ANT_NUM; j++) { ants[j].Search(); } //更新环境信息素 Updateinfo(); } bestSuperAnt.length = 1 << 21; // 从起点出发多只蚂蚁 for (int j = 0; j < TNUM; j++) { for (int i = 0; i < ANT_NUM; i++) { SuperAnts[i].Search(); if (SuperAnts[i].length < bestSuperAnt.length) { bestSuperAnt = SuperAnts[i]; } } } for (int i = 0; i < CITY_NUM; i++) { if (i) cout << "->"; cout << bestSuperAnt.Path[i]; } cout << endl; cout << "距离为 : "; cout << bestSuperAnt.length << endl; } }; // 贪心法的语句 double TanXin(int from, int* visit, double sum, int* shunXv, int pointNum) { int flag = true; for (int i = 0; i < NUM; i++) { if (visit[i] == 0) { flag = false; break; } } if (flag) return sum; double min = 1000000; int to; for (int i = 0; i < NUM; i++) { if (dis[from][i] < min && visit[i] == 0) { min = dis[from][i]; to = i; } } sum += dis[from][to]; visit[to] = 1; shunXv[pointNum++] = to; return TanXin(to, visit, sum, shunXv, pointNum); } double qiujv(int x1, int y1, int x2, int y2) { return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2)); } struct point { int x; int y; }; // 主函数 int main() { // fanWei 代表范围 // chuShi 代表起始位置, 即0 int fanWei; int chuShi = 0; cout << "请输入范围 : "; cin >> fanWei; point point[NUM]; for (int i = 0; i < NUM; i++) { point[i].x = random(fanWei); point[i].y = random(fanWei); } for (int i = 0; i < NUM; i++) { for (int j = 0; j < NUM; j++) { dis[i][j] = qiujv(point[i].x, point[i].y, point[j].x, point[j].y); } } double min = 100000; // 最小值 int to; //要去的 double sum = 0; //总数 int shunXv[NUM] = { 0 }; // 顺序 int visit[NUM] = { 0 }; // 储存访问过的点 for (int i = 1; i < NUM; i++) { if (dis[0][i] < min) { min = dis[0][i]; to = i; } } sum += dis[0][to]; shunXv[1] = to; visit[0] = 1; visit[to] = 1; tanXindis = TanXin(to, visit, sum, shunXv, 2); cout << endl; cout << "*********** 贪心的结果 **********" << endl; for (int i = 0; i < NUM; i++) { if (i) cout << "->"; cout << shunXv[i]; } cout << endl; cout << "距离为 : " << tanXindis << endl; cout << endl; cout << "*********** 蚁群的结果 **********" << endl; TSP tsp; tsp.Init(); tsp.Search(); return 0; }
 2019-03-28   瞎搞    算法 

poj-2253 poj-1797 最短路变形

poj-2253 题意 复制一下别人的题意,有两只青蛙和若干块石头,现在已知这些东西的坐标,两只青蛙A坐标和青蛙B坐标是第一个和第二个坐标,现在A青蛙想要到B青蛙那里去,并且A青蛙可以借助任意石头的跳跃,而从A到B有若干通路,问从A到B的所有通路上的最大边 从a到b有n条路径, 寻找n条路经中边最大长度最小的 code /********************************************************** > File Name : 2253.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 19 18:47:31 **********************************************************/ #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> #define INF 1<<28 using namespace std; typedef pair<int , int> point; point ps[250]; int n; double d[250]; bool used[250]; double map[250][250]; void getdis(){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ map[i][j] = INF; } } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == j){ map[i][j] = 0; continue; }else{ double dis; dis = sqrt(pow((double)(ps[i].first - ps[j].first), 2) + pow((double)(ps[i].second - ps[j].second), 2)); map[i][j] = dis; map[j][i] = dis; } } } } void diji(int f){ fill(d, d + n, INF); memset(used, 0, sizeof(used)); d[f] = 0; while(true){ int v = -1; double mind = INF; for(int u = 0; u < n; u++){ if(!used[u] && (v == - 1 || d[u] < mind)){ v = u; mind = d[u]; } } if(v == -1) break; used[v] = 1; for(int u = 0; u < n; u++){ // 更新的是f号石头到u号石头最长边中的最小边 d[u] = min(d[u], max(d[v],map[v][u])); } } } int main(){ int kase = 0; while(cin >> n){ if(n == 0) break; int a, b; for(int i = 0; i < n; i++){ cin >> a >> b; ps[i].first = a; ps[i].second = b; } getdis(); diji(0); printf("Scenario #%d\n", ++kase); printf("Frog Distance = %.3f", d[1]); printf("\n"); printf("\n"); } return 0; } 关于Dijkstra成立条件的一篇博文 poj-1797 题意 上一个是找所有路径中最长路径最短的, 这个是找所有路径中最短路径最长的 code /********************************************************** > File Name : 1797.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 19 20:58:42 **********************************************************/ #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> #include <queue> #define INF 1<<28 #define MINF -1 using namespace std; int map[1050][1050]; int book[1050]; int n, k; int d[1050]; void diji(){ for(int i = 0; i < n; i++){ d[i] = map[0][i]; book[i] = 0; } d[0] = 0; for(int i = 0; i < n; i++){ int maxd = -1; int t; for(int j = 0; j < n; j++){ if(!book[j] && d[j] > maxd){ maxd = d[j]; t = j; } } book[t] = 1; for(int j = 1; j < n; j++){ if(!book[j] && d[j] < min(d[t], map[t][j])){ d[j] = min(d[t], map[t][j]); } } } } int main(){ int kase = 0; int num; cin >> num; while(num--){ cin >> n >> k; int a, b, c; memset(map, -1, sizeof(map)); for(int i = 0; i < k; i++){ cin >> a >> b >> c; map[a - 1][b - 1] = c; map[b - 1][a - 1] = c; } diji(); /* for(int i = 0; i < n; i++){ cout << d[i] << " "; } */ printf("Scenario #%d:\n", ++kase); printf("%d\n\n", d[n - 1]); } return 0; }
 2019-03-28   acm    最短路 

poj-2384 简单最短路问题

link Dijkstra无优化版本 (AC) /********************************************************** > File Name : 2384.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 18 19:01:57 **********************************************************/ // 邻接矩阵表示 141ms #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> #define INF 1<<28 using namespace std; int map[1050][1050]; int t, n; int d[1050]; bool used[1050]; void bell(int f){ fill(d, d + n + 1, INF); memset(used, 0, sizeof(used)); d[f] = 0; while(true){ int v = -1; for(int u = 1; u < n + 1; u++){ if (!used[u] && (v == -1 || d[u] < d[v])) v = u; } if(v == -1) break; used[v] = true; for(int u = 1; u < n + 1; u++){ d[u] = min(d[u], d[v] + map[v][u]); } } } int main(){ while(cin >> t >> n){ int a, b, c; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < n + 1; j++) { map[i][j] = INF; } } for(int i = 0; i < t; i++){ cin >> a >> b >> c; if(c < map[a][b]){ map[a][b] = c; map[b][a] = c; } } for(int i = 0; i < n + 1; i++){ map[i][i] = 0; } bell(1); cout << d[n] << endl; } return 0; } Dijkstra 邻接表 + 堆优化 (AC) /********************************************************** > File Name : 2384.cpp > Author : Wqr_ > Mail : xueduanwei@126.com > Created Time : 19 03 18 19:01:57 **********************************************************/ // 邻接表表示+堆优化 141ms #include <iostream> #include <cmath> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <cstdio> #include <string> #include <vector> #include <queue> #define INF 1<<28 using namespace std; struct road{int to, cost; }; // first为最短距离, second为编号 typedef pair<int, int> P; int n, t; vector<road> G[1010]; int d[1010]; void dij(int f){ //优先队列 首先按照pair.first进行排序, first相同时按照second进行排序 priority_queue<P, vector<P>, greater<P> > q; fill(d, d + n + 1, INF); d[f] = 0; q.push(P(0, f)); while (!q.empty()) { //每次选择出距离f最近的点为v P p = q.top(); q.pop(); int v = p.second; if(d[v] < p.first) continue; // 以v为跳板更新其他边的最小距离 for(int i = 0; i < G[v].size(); i++){ road e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; q.push(P(d[e.to], e.to)); } } } } int main() { while (cin >> t >> n) { int a, b, c; // 邻接表的输入 for (int i = 0; i < t; i++) { cin >> a >> b >> c; road tmp; tmp.to = b; tmp.cost = c; //将各个边push进G[a] G[a].push_back(tmp); tmp.to = a; tmp.cost = c; //将各个边push进G[b] G[b].push_back(tmp); } dij(1); cout << d[n] << endl; } return 0; }
 2019-03-28   acm    最短路