1's Issues
Dij及堆优化
分析
Dij算法是基于广搜,松弛的时候有点贪心和动态规划的**。
使用邻接矩阵实现的dijkstra算法的复杂度是O(V²)。
使用邻接表,更新最短距离只需要访问每条边一次,因此这部分的复杂度是O(E)。但是每次要枚举所有的顶点来查找下一个使用的顶点,因此最终复杂度还是O(V²)。
综上:在|E|比较小时,大部分的时间都花在了查找下一个使用的顶点上,因此需要使用合适的数据结构进行优化。
优先队列+dijkstra算法:
总时间复杂度=找最短距离 u 的时间复杂度 + 更新距离 dist[v] 的时间复杂度
对于无向图G(V,E):
找最短距离的时间复杂度为O(
由于图共有E条边,每条边最多被更新2次(1条边2个端点),因此更新距离的时间复杂度为$O(2*|E|)$。
因此,总时间复杂度$=O(2|E|+|V|^2/2)$*
实际情况中经常会遇到
因此,如果我们能够优化 findMIN部分,即可大大优化稀疏图下的dijkstra算法,findMIN的部分优化方法很多,最简单的就是用二分搜索$O(logN)$代替线性搜索
这里我们将集合Q转化成一个优先队列(priority queue),这样findMIN的时间复杂度变成了O(1),而每次更新priority queue需要花费$O(log|V|)$
综上,采用优先队列之后,总时间复杂度=$O(2|E|+|V|log|V|)$,这样的优化对于稀疏图(|V|^2>>|E|)来说,尤为有效
用邻接矩阵的Dijkstra算法的代码:
int dis[maxn];
bool visit[maxn];
int n,m; //V,E
void Dijkstra( int s )
{
int i,v,u;
for( i=1; i<=n; ++i )
{
visit[i]=false;
dis[i]=mp[1][i];
}
dis[s]=0;
while( true )
{
v=-1;
for( u=1; u<=n; ++u )
if( !visit[u] && ( v==-1 || dis[u]<dis[v]) )
v=u;
if( v==-1 ) break;
visit[v]=true;
for( u=1; u<=n; u++ )
dis[u]= min( dis[u],dis[v]+mp[v][u] );
}
}
使用STL的priority_queue实现。在每次更新时往堆里插入当前最短距离和顶点的值对。
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int Ni = 10000;
const int INF = 1<<27;
struct node{
int x,d;
node(){}
node(int a,int b){x=a;d=b;}
bool operator < (const node & a) const
{
if(d==a.d) return x<a.x;
else return d > a.d;
}
};
vector<node> eg[Ni];
int dis[Ni],n;
void Dijkstra(int s)
{
int i;
for(i=0;i<=n;i++) dis[i]=INF;
dis[s]=0;
//用优先队列优化
priority_queue<node> q;
q.push(node(s,dis[s]));
while(!q.empty())
{
node x=q.top();q.pop();
for(i=0;i<eg[x.x].size();i++)
{
node y=eg[x.x][i];
if(dis[y.x]>x.d+y.d)
{
dis[y.x]=x.d+y.d;
q.push(node(y.x,dis[y.x]));
}
}
}
}
int main()
{
int a,b,d,m;
while(scanf("%d%d",&n,&m),n+m)
{
for(int i=0;i<=n;i++) eg[i].clear();
while(m--)
{
scanf("%d%d%d",&a,&b,&d);
eg[a].push_back(node(b,d));
eg[b].push_back(node(a,d));
}
Dijkstra(1);
printf("%d\n",dis[n]);
}
return 0;
}
/*
6 6
1 2 2
3 2 4
1 4 5
2 5 2
3 6 3
5 6 3
*/
原网址:https://blog.csdn.net/major_zhang/article/details/72519233
Bellman-ford
适用条件&范围:
- 单源最短路径(从源点s到其它所有顶点v);
- 有向图&无向图(无向图可以看作$(u,v),(v,u)$同属于边集E的有向图);
- 边权可正可负(如有负权回路输出错误提示);
- 差分约束系统;
Bellman-Ford算法的流程如下:
-
给定图$G(V, E)$(其中$V、E$分别为图$G$的顶点集与边集),源点$s$,数组$Distant[i]$记录从源点s到顶点i的路径长度,初始化数组$Distant[s]$为0;
-
以下操作循环执行至多$n-1$次,$n$为顶点数:
- 对于每一条边$e(u, v)$,
如果$Distant[u] + w(u, v) < Distant[v]$,
则 $Distant[v] = Distant[u]+w(u, v)$。
其中$w(u, v)$为边$e(u,v)$的权值; - 若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;
- 对于每一条边$e(u, v)$,
-
对于每一条边$e(u, v)$,如果存在$Distant[u] + w(u, v) < Distant[v]$的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组$Distant[n]$中记录的就是源点$s$到各顶点的最短路径长度。
可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为$O(V*E)$.
Bellman-Ford算法可以大致分为三个部分
- 第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为 0,其它的点的值设为无穷大(表示不可达)。
- 第二,进行循环,循环下标为从1到$n-1$(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
- 第三,遍历途中所有的边$edge(u,v)$,判断是否存在这样情况:
$d(v) > d (u) + w(u,v)$
则返回false,表示途中存在从源点可达的权为负的回路。
之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。
与dij的比较
在更新路径的操作上,和迪杰斯特拉算法大同小异,但是不同于迪杰斯特拉算法,他不是选取最小的边进行选择,而是根据每一条边,依次对Distence数组进行更新,所以会访问很多访问过的点,借此重复不遗漏的更新距离数组,也就是规划起点到当前访问的相邻点的问题。
核心代码:
struct Node{
int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];
bool Bellman(int s){
fill(d,d+MAXV,INF);
d[s]=0;
for(int i=0;i<n-1;i++){
for(int u=0;u<n;u++){
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v]){
d[v]=d[u]+dis;
}
}
}
}
for(int u=0;u<n;u++){
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(d[u]+dis<d[v]){
return false;
}
}
}
return true;
}
图论基础
一、基本术语
图(graph):图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中的顶点的集合,E是图G中边的集合。
无向边(Edge):若顶点V1到V2之间的边没有方向,则称这条边为无向边。
无向图(Undirected graphs):图中任意两个顶点之间的边都是无向边。(A,D)=(D,A)对于无向图G来说,G1=(V1,{E1}),其中顶点集合V1={A,B,C,D};边集和E1={(A,B),(B,C),(C,D),(D,A),(A,C)}
有向边:若从顶点V1到V2的边有方向,则称这条边为有向边,也称弧(Arc)。用<V1,V2>表示,V1为狐尾(Tail),V2为弧头(Head)。(V1,V2)≠(V2,V1)。
有向图(Directed graphs):图中任意两个顶点之间的边都是有向边。
注意:无向边用“()”,而有向边用“< >”表示。
简单图:图中不存在顶点到其自身的边,且同一条边不重复出现。
无向完全图:无向图中,任意两个顶点之间都存在边。
有向完全图:有向图中,任意两个顶点之间都存在方向互为相反的两条弧。
稀疏图:有很少条边。
稠密图:有很多条边。
权(Weight):与图的边或弧相关的数。
网(Network):带权的图。
路径的长度:一条路径上边或弧的数量。
二、图的存储结构
-
1.邻接矩阵:用两个数组,一个数组保存顶点集,一个数组保存边集。
图的邻接矩阵存储的结构:
#define maxvex 100
typedef struct
{
char vexs[maxvex];
int arc[maxvex][maxvex];
int vertex,edges;
}MGraph;
无向图的创建代码:
#define maxvexs 100
#define infinity 65535//用65535来表示∞
typedef struct
{
char vexs[maxvexs];
int arc[maxvexs][maxvexs];
int vertexes,edges;
}mgraph;
void creatgraph(mgraph *g)
{
int i,j,k,w;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&g->vertexes,&g->edges);
for(i=0;i<g->vertexes;i++)//读入顶点信息,建立顶点表
scanf("%c",&g->vexs[i]);
for(i=0;i<g->vertexes;i++)
for(j=0;j<g->vertexes;j++)
g->arc[i][j]=infinity;//初始化邻接矩阵
for(k=0;k<g->vertexes;k++)//读入edges条边,建立邻接矩阵
{
printf("输入边(Vi,vj)上的下标i,下标j,和权w:\n");
scanf("%d%d%d",&i,&j,&w);
g->arc[i][j]=w;
g->arc[j][i]=w;//无向图,矩阵对称
}
}
-
2.邻接表:数组与链表相结合的存储方法。
对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。
邻接表结点定义
typedef struct EdgeNode
{
int adjvex; //邻接点域,存储该顶点对应的下标
int weight; //用于存储权值,对于非网图可以不需要
struct EdgeNode *next; //链域,指向下一个邻接点
}EdgeNode;//边表结点
typedef struct VertexNode //顶点表结点
{
char data; //顶点域,存储顶点信息
EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes,numEdges;//图中当前顶点数和边数
}GraphAdjList;
-
3.边集数组
(1)边集数组定义
边集数组是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元边的个数要等于图中的边的条数,每个元素用来存储一条边的起点、终点和权(若含有权的话)。每个元素包含三个属性,因此建议先定义为结构体,再定义结构体数组。对于无向图,可选定变得任一端为起点或终点。各边在数组中的次序可以任意安排,也可以根据具体要求而定。
struct Edge{
int s;
int e;
int length;
}Edge[100];
(2)边集数组的特征
在边集数组中查找一条边或一个顶点的都需要扫描整个数组,所以其时间复杂度为O(e)。边集数组适合那些对边依次进行处理的运算,不适合对顶点的运算和对任一条边的运算。边集数组的表示通常包括一个边集数组和一个顶点 数组,所以其空间复杂度为O(n+e)。从空间复杂度上讲,边集数组也适合表示稀疏图。
-
4.前向星:前向星是一种通过储存边信息的方式储存图的结构。
读入每条边的信息(起点、终点、权值)
存放在数组里
按照起点排序
通常会有一个head数组,记录每个起点上的第一条边。
Floyd
全局最短路
一篇解释很好的文章:https://www.cnblogs.com/wangyuliang/p/9216365.html
- 全局最短路
用一句话概括就是:从 i 号顶点到 j 号顶点只经过前 k 号点的最短路程。
核心代码:
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
- 最小环问题
都比较容易得到从 u 到 v 经过中间某一些结点的最短路,但是我们得确保回来的时候,不能经过那些结点,这样我们就需要改一下 floyd 算法了。
核心代码:
int mincircle = infinity;
Dist = Graph;
for(int k=0;k<nVertex;++k){
//新增部分:
for(int i=0;i<k;++i)
for(int j=0;j<i;++j)
mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);
//通常的 floyd 部分:
for(int i=0;i<nVertex;++i)
for(int j=0;j<i;++j){
int temp = Dist[i][k] + Disk[k][j];
if(temp < Dist[i][j])
Dist[i][j] = Dist[j][i] = temp;
}
}
- Floyd 算法保证了最外层循环到 k 时所有顶点间已求得以 0…k-1 为中间点的最短路径。
- 新增部分在前面:因为在之前的最短路径更新过程中, k 没有参与更新,所以dist[i][j]所表示的路径中不会有点 k ,即一定为一个环;
一个环至少有3个顶点,设某环编号最大的顶点为 L ,在环中直接与之相连的两个顶点编号分别为 M 和 N (M,N < L),则最大编号为 L 的最小环长度:
Graph(M,L) + Graph(N,L) + Dist(M,N)
其中 Dist(M,N) 表示以 0…L-1 号顶点为中间点时的最短路径,刚好符合 Floyd 算法最外层循环到 k=L 时的情况,则此时对 M 和 N 循环所有编号小于 L 的顶点组合即可找到最大编号为 L 的最小环。再经过最外层 k 的循环,即可找到整个图的最小环。
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 150;
int n,m,a,b,c;
int mp[maxn][maxn];//表示的正常从u到v经过k的最短路
int A[maxn][maxn];//表示的是不经过k的时候回来的时候的最短路
int floyd()
{
int retmin = INF;
for(int k = 1;k <= n;k++)
{
for(int i = 1;i < k;i++)//假设k为最大的结点,进行遍历优化,并且最后也不会包含最大的结点n
{
for(int j = i + 1;j < k;j++)
{
//为什么不更新优化mp数组呢,是因为这是一个暴力的循环,总能够找到最小值!
int tmp = A[i][j] + mp[i][k] + mp[k][j];
//这个时候A[i][j]还没有更新k结点!!因为下一层才开始更新……
if(tmp < retmin)retmin = tmp;
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(A[i][j] > A[i][k] + A[k][j])
A[i][j] = A[i][k] + A[k][j];
}
}
}
return retmin;
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
//初始化
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
mp[i][j] = A[i][j] = INF;
}
}
//输入距离进行更新,防止重边的影响,自动定义为双向边
for(int i = 1;i <= m;i++)
{
scanf("%d%d%d",&a,&b,&c);
mp[a][b] = mp[b][a] = A[a][b] = A[b][a] = min(mp[a][b],c);
}
//进行floyd算法,寻找最小环
int s = floyd();
if(s == INF)
printf("It's impossible.\n");
else
printf("%d\n",s);
}
return 0;
Dij和Floyd比较
Dij和Floyd的比较
-
- Dij不适用于负权边
- Floyd不适用于负权环
-
- Dij适用于单源路径问题(简单来说就是确定一个源点s 求s到1,2,3……)
- Floyd适用于多源点路径问题 就是说在n个点中任选两个点 求这两个点之间的最短路径
-
- Dij的**是“插边”
dp方程式:dis[u]=min(dis[u],e[v][u]+dis[v])
v是离源点最近且没被标记的那个点 - Floyd的**是“插点”
强行插入一个点k 注意在循环的时候k要放在最外面(因为floyd的**便是令 k 循环n次 强行插入到(i,j)中去)
dp方程式: e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
e[i][j]就是指从i到j的距离
- Dij的**是“插边”
-
- dij的时间复杂度是O(n^2),经过堆的优化可以达到O((m+n)log(n));
- floyd的时间复杂度是O(n^3)
原文链接:https://blog.csdn.net/XXXTANTACION/article/details/100099854
核心代码比较:
Floyd:是最简单的最短路径算法,可以计算图中任意两点间的最短路径 folyd算法的时间复杂度是O(N3),如果是一个没有边权的图,把相连的两点 间的距离设为dist[i][j] = 1,不相连的两点设为无穷大,用 floyd算法可以判断i,j两点是否有路径相连。
void floyd()
{
for(int k = 0; k < n; k ++){ //作为循环中间点的k必须放在最外一层循环
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if(dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j]; //dist[i][j]得出的是i到j的最短路径
}
}
}
}
}
Dij:用来计算从一个点到其他所有点的最短路径的算法,复杂度O(N2)。
void dijkstra(int s) //s是起点
{
memset(visit, false, sizeof(visit));
visit[s] = true;
for(int i = 0; i < n; i ++){
dist[i] = graph[s][i];
}
int index;
for(int i = 1; i < n; i ++){
int mincost = INF;
for(int j = 0; j < n; j ++){
if(!visit[j] && dist[j] < mincost){
mincost = dist[j];
index = j;
}
}
visit[index] = true;
for(int j = 0; j < n; j ++){
if(!visit[j] && dist[j] > dist[index] + graph[index][j]){
dist[j] = dist[index] + graph[index][j];
}
}
}
}
原文链接:https://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html
最小生成树
prime算法
1.清空生成树,任取一个顶点加入生成树
2.在那些一个端点在生成树里,另一个端点不在生成树里的边中,选取一条权最小的边,将它和另一个端点加进生成树
3.重复步骤2,直到所有的顶点都进入了生成树为止,此时的生成树就是最小生成树
核心代码:
int prime(int index)
{
int index;
int sum = 0;
memset(visit, false, sizeof(visit));
visit[cur] = true;
for(int i = 0; i < m; i ++){
dist[i] = graph[cur][i];
}
for(int i = 1; i < m; i ++){
int mincost = INF;
for(int j = 0; j < m; j ++){
if(!visit[j] && dist[j] < mincost){
mincost = dist[j];
index = j;
}
}
visit[index] = true;
sum += mincost;
for(int j = 0; j < m; j ++){
if(!visit[j] && dist[j] > graph[index][j]){
dist[j] = graph[index][j];
}
}
}
return sum;
}
堆优化的prime:
堆优化实际上就是对于每一次拓展的边加入到一个小根堆中,即找最小边的时候直接用堆来储存
核心代码:
void queue_prim()
{
//以节点1为起点进行扩展安全边 生成最小树
priority_queue<node>que;
while(!que.empty())
que.pop(); //初始化清空优先队列 维护一个小根堆
//这样每次找安全边的速度就提高了
ans = 0;
memset(vis, false, sizeof(vis));
for(int i=0; i<q[1].size(); i++){
que.push(q[1][i]); //将起点的所有连接边全部加入队列中来
}
vis[1]=true;
int edge=n-1;//边数
node cur;
while(edge--)
{
cur = que.top();
que.pop();//这个地方需要注意一下
//并不是每个从优先队列取出来的边都是可以加到生成树上去的
if(vis[cur.v]==true){
while(vis[cur.v]){
cur=que.top(); que.pop();
}
}
ans = ans+cur.w; //printf("%d-- ", cur.w );
vis[cur.v]=true; //加入生成树的该点将被标记访问
for(int i=0; i<q[cur.v].size(); i++){
if(vis[ q[cur.v][i].v ]==false) //当前加入生成树的点可以扩充出的边指向的节点
que.push(q[cur.v][i]);//如果没有被访问才会加入到队列当中来
}
}
}
kruskal算法
在剩下的所有未选取的边中,找最小边,如果和已选取的边构成回路,则放弃,选取次小边。
//把每条边成为一个结构体,包括起点、终点和权值
typedef struct node
{
int val;
int start;
int end;
}edge[SIZE * SIZE / 2];
//把每个元素初始化为一个集合
void make_set()
{
for(int i = 0; i < n; i ++){
father[i] = i;
rank[i] = 1;
}
return ;
}
//查找一个元素所在的集合,即找到祖先
int find_set(int x)
{
if(x != father[x]){
father[x] = find_set(father[x]);
}
return father[x];
}
//合并x,y所在的两个集合:利用Find_Set找到其中两个
//集合的祖先,将一个集合的祖先指向另一个集合的祖先。
void Union(int x, int y)
{
x = find_set(x);
y = find_set(y);
if(x == y){
return ;
}
if(rank[x] < rank[y]){
father[x] = find_set(y);
}
else{
if(rank[x] == rank[y]){
rank[x] ++;
}
father[y] = find_set(x);
}
return ;
}
bool cmp(pnode a, pnode b)
{
return a.val < b.val;
}
int kruskal(int n) //n为边的数量
{
int sum = 0;
make_set();
for(int i = 0; i < n; i ++){ //从权最小的边开始加进图中
if(find_set(edge[i].start) != find_set(edge[i].end)){
Union(edge[i].start, edge[i].end);
sum += edge[i].val;
}
}
return sum;
}
Agri-Net的Kruskal算法+并查集实现
算法复杂度分析
对所有的边进行排序,排序复杂度为$O(mlogm)$,随后对边进行合并,合并使用并查集,并查集使用link by size的方式实现,同时在find函数实现了路径压缩。
- 每个元素第一次被执行find操作需要的复杂度为$O(logm)$,总共m个元素
- 如果已经有n-1条边,那么可以停止循环,时间复杂度为$O(nlogm)$
- 时间复杂度为$O(mlogm+nlogm)$
而存在最小生成树中的情况下,图至少有$n-1$条边,即$m>=n-1$,于是整体复杂度为$O(mlogn)$。即使对并查集做了路径压缩的优化,但是前面的排序过程仍然是算法的瓶颈,因此算法复杂度仍然是$O(mlogn)$。
核心代码
// 并查集
struct QuickUnion {
vector<int> sz; // 表示集合大小的数组
vector<int> parent; // 表示一个顶点的所在集合的根节点
QuickUnion(const int n) {
sz.assign(n,0);
for (int i = 0; i < n; ++i)
parent.push_back(i);
}
// 寻找一个节点的根节点
int find(const int x) {
if (x != parent[x])
parent[x] = find(parent[x]);// 路径压缩
return parent[x];
}
// 合并两个节点所在的集合
bool unionNode(const int x, const int y) {
int p1 = find(x);
int p2 = find(y);
if (p1 == p2)
return false;
if (sz[p1] >= sz[p2]){
sz[p1] += sz[p2];
parent[p2] = p1;
}
else{
sz[p2] += sz[p1];
parent[p1] = p2;
}
return true;
}
};
int Kruskal(vector<Edge> graph, int nodeNum) {
QuickUnion qu(nodeNum);
sort(graph.begin(),graph.end());
int MSTWeight = 0;
int edgeCount = 0;
for (auto&e : graph){
if (qu.unionNode(e.from, e.to)){
MSTWeight += e.weight;
++edgeCount;
if (edgeCount == nodeNum - 1)
break;
}
}
return MSTWeight;
}
原文链接:https://blog.csdn.net/t46414704152abc/article/details/83896339
最快最好用的——spfa算法
原文:http://www.layz.net/LAOJ/suanfa/s9-4.html
回头补整理过的。
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.