新世界

写个文章记录一下基本的socket的使用

一、面向连接的编程TCP

1、服务器端：

首先建立socket

sockfd = socket(AF_INET, SOCK_STREAM, 0)

第二个参数说明是面向连接的编程，如果返回-1代表出错，否则返回socket描述符的值；
然后本机配置一个sockaddr_in类型的地址

myaddr.sin_family = AF_INET;  
myaddr.sin_port = htons(SERVER_PORT);  
myaddr.sin_addr.s_addr = INADDR_ANY;//这个值代表自动为这个字段填入本机的IP地址  
memset(&myaddr.sin_zero, 0, sizeof(myaddr.sin_zero));

接下来要将socket和配置的地址绑定

bind(sockfd, (struct sockaddr *)&myaddr, sizeof(struct sockaddr))

如果返回值为-1代表出错；
接下来设置同时接收请求的最大数量

listen(sockfd, NUM)

NUM代表最大的同时请求的数量，这个函数在tcp连接中才有用 ...

恩，本篇文章再写一点深入的思考。忽然发现我的博客开始走找各种被人忽略的细节的路线了。今天要为大家带来的是差分约束的两个题，并且会为大家说明一下自己做这题时候的思考和网上流传的一些错误，不想让网上抄来抄去的东西误导了大家的思路。OJ数据弱，这个是真的，题目那么多，不能保证每个题测试数据的质量，所以很多错误的程序也能过，导致了大家可能把错误的思路也认为是正确的了。恩，下面开始正文。

POJ 3169

题意：n头牛站在x轴上，并且x[1]<=x[2]<=...<=x[n]，然后给定了一些喜欢的关系和讨厌的关系，喜欢的关系是（a，b，c）代表牛a和牛b的距离不才能超过c，讨厌的关系也是（a，b，c）代表牛a和牛b的距离至少是c，然后求牛1和牛n的最大距离是多少。如果没有合法的站位，输出-1；如果牛1和牛n可以无穷远，输出-2；否则输出牛1和牛n的最大距离。

这个题看上去很水的，差分约束的题，按照“最长路求最小值，最短路求最大值”的理论建图就行了。需要注意的一个细节就是，如果同时满足没有合法的站位和牛n牛1可以相距无穷远，那么按照题意应该是输出-1的 ...

写个博客记录一下最短路的几种算法，尽量做最正确的解答，减少大家的疑惑，网上有好多讲的都抄来抄去，还有好多讲的都是错误的。。。

熟悉的最短路算法就几种：bellman-ford，dijkstra，spfa，floyd，下面针对这几个算法具体解析一下。 首先说明一点，就是关于负环的问题。
bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。
dijkstra只能用于边权都为正的图中。
spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。
floyd可以用于有负权的图中，即使有负环，算法也可以检测出来。

任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。这几点非常重要，可以在我下面的讲解中体会。

1、dijkstra

这个最简单，只能在边权都为正的图中用这个算法，不论是有向图还是无向图。算法是个贪心的过程，每次拿出一个没有被标记过的距离最小的顶点，并从这个点进行扩展，也就是尝试松弛从这个点出发的每条边。为什么一定要用在正权图中呢？因为算法的过程相当于把整个图中的点一个一个加入到“处理完”集合S的过程，并且处理完集合中的点的距离一定是从源点到该点的最小距离。如果图中有负权，会导致一个进入集合中的点可能在后面的过程中距离值变得更小，算法就错了。举个例子来说：有向图 ...

偶是个韩国电影爱好者，不能说是电影迷吧，对电影没有那么强烈的热爱，只是喜欢而已，而且本人也不是追星族。在这里只是列出一些我印象中比较深刻的一些韩国电影，然后做一些极简短的介绍。

首先声明，本人男，喜欢看一些引人深思的韩国电影，喜欢有一点暴力但不是特别血腥的电影。情感片我一般不会主动找这些影片看，但是如果碰到了还是会看一下，韩国电影表达感情很细腻，能触碰到内心深处最柔软的部分，我觉得看电影可以提高情商的，对做人处事了解世界有不少增益。以下我列出的韩国电影我强烈推荐的我都觉得非常值得看，看完之后会有很多体会和感悟，是值得细细品味的电影。每个电影的介绍比较简短，以防一些不喜欢剧透的朋友失去观看的兴趣。

1、《舞后》

这个电影非常好看啊，主角是黄政民和严正花，在剧中两人是真名出演，讲述关于亲情和梦想的故事，在我心里评分100，强烈推荐的电影。

2、《大叔》

主角叫元斌，是个帅气的小伙，在剧中被叫成大叔，电影讲述他为了救一个邻家女孩发生的一系列故事，主角的身手太帅气了，简单暴力，是我喜欢的类型，强烈推荐。

3、《假如爱有天意》

这个是我很早看的一个电影，非常感人，记得女主很漂亮，影片表达的唯美的爱情，记得我看完这个电影之后很久一段时间都不能听这个电影的主题曲，一听就会想起剧中的情节，在我心里评分100，强烈推荐 ...

题意：一个无向图，求从一个顶点到另一个顶点的恰好经过k条边的最短路径，可能有自环，无重边。

分析：这个题其实就是矩阵乘法，用了dp的思想，dp[k][i][j]代表恰好经过k条边的i到j的最短路，那么dp[k][i][j]=min{dp[k-1][i][p]+g[p][j]}（其中g是原图）。可以用矩阵乘法来做，因为对于dp[k-1][i][j]来说，只要乘以一次原图矩阵，就相当于做了一次转移，得到的就是dp[k][][]矩阵。我想说这个题除了状态设计和floyd稍微沾了一点边之外，其他一点关系都没有了，竟然看到网上好多人用写floyd的循环顺序来写这个题，真是令人费解，这个题只是改了矩阵乘法的最内层，改变了矩阵乘法的运算规则，和floyd真的没关系啊！！！

另外，矩阵乘法的规则和在图中求一个点到另一个点的恰好经过k条边的方法数的规则是一样的，二者的状态转移方程也是一样的，所以矩阵乘法不需要经过任何修改就能做这种求恰好经过k条边的方法数的题，而不用像这个题还得做些修改。这些题都需要注意初始化的东西 ...

eclipse + cdt + mingw的一些配置 下载标准版本的eclipse（我用的是4.3.0版本的，也叫kepler），下载对应版本的CDT(8.2.0)，安装mingw，我是用mingw-get-inst-20120426.exe装的（这个版本我用的比较舒服，如果在官网上下载mingw的话，安装完可能缺少libiconv2，它是个windows运行的dll库，一般电脑上貌似没有这个库，如果没有它的话不能执行make命令），选装gcc和g++两个组件，如果按照默认路径（C:\MinGW）装可能会碰到少一点的问题。

cdt有两种下载方式，可以在eclipse的help中通过install安装，也可以在网上下载，然后把下载完的压缩包解压，把里面的features文件夹和plugins文件夹复制到eclipse的根目录中，和eclipse的根目录中的features、plugins文件夹合并就行。

1、头文件unresolved问题
这个可以通过在环境变量中设置PATH=MinGW\bin来解决，如果设置了这个path的话，那么eclipse会自动找mingw的一些头文件库，加入到工程中的include文件夹下面（刚创建工程的时候只有一个src目录，没有include目录）。不幸的是，有的时候可能不起作用，我的就是加入了变量，但是不管用，后来把变量删了，又重新加入了一次才管用 ...

题意：一个无向图，所有边权为正，求这个无向图中的一个权值最小的环（环的权值定义为环中所有边权值的和）。要求环的顶点数至少为3个，且图中可能存在重边。

分析：这个题我最开始只有搜索的想法，后来看到了floyd的做法，才折服了，向强大的floyd致敬！ 这个题可以这么想，抛开floyd的思路，我们知道每个环中都有一个顶点标号最大的顶点（比如为k）。我们可以枚举这个顶点，枚举完这个顶点之后我们再枚举另外两个和它相邻的顶点i和j（i，j < k）。如果这个时候我们知道i到j的不经过k的最短路（设为p），那么我们就可以把边i->k，k->j和路径p组合起来，成为一个环，如果这个环的权值小于当前求出的所有环里面的最小权值的话，那么就更新一下最小值，并记录路径。

恩，这个思路看上去是挺好的，但是我们怎么求i到j的不经过k的最短路呢？想到了什么？floyd！ floyd的本质是个dp，dp[k][i][j]代表i到j的中间节点（不包括i和j）都在区间[1，k]时，i到j的最短路。floyd算法的最外层循环是个从小到大枚举k的过程，当最外层刚刚进入第k次循环的时候 ...

题意：一个图，有两种边，一种是双向边，权值为正，一种是单向边，权值为负。
问能否在图中找到一个负环。

分析：典型的找负环的题，但是这个题没有规定起点，所以直接从点1开始做bf是错误的。
bellman-ford算法可以判断一个从源点可达的环，那这个题需要做n次bf吗？
其实可以建立一个源，从源向每个图中的点引一条任意权值的边（不必为0），然后用bf就行了。
本质上就是初始化和经典的初始化不同，细节见代码。

/*
    POJ 3259
    code by heifrank
*/
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int MV = 505;

vector< pair<int, int> > G[MV];
int d ...

恩，这个是我搭建起这个博客写的第一篇文章

希望能一直把这个博客写下去，我老婆也有一篇博客，马上要搭起来了，
和老婆一起写应该是挺开心的事情吧，
研究生的日子要好好过，多学点技术，老婆是个技术白痴，
好多东西得我帮她弄，哎，苦逼技术男，木有办法。