发表于   |   分类于 生活 , 项目开发日志   |   暂无评论

synctoqq发布

synctoqq

实现的功能：

当github上发起一个issue时可以通过qq机器人发送到qq群中，并自动设置精华消息以及发布群公告

实现流程：

github发起issue ，程序接收issue的json数据， WebSocket连接qq机器人， 通过api发送消息，设置精华消息，以及发送群公告

下载链接：

https://github.com/heky12356/synctoqq/releases/tag/build

食用教程：

https://github.com/heky12356/synctoqq/blob/main/README.md

更新日志：

https://github.com/io-club/share/issues/6

碎碎念：

感觉很久没有这种解决问题，然后做一个程序，或者是不断找资料来回折腾的感觉了。
也很久没有写过类似于以前那种偏向于解决实际问题或者推荐软件的选题了。
真的很感谢这次io社的外包机会，让我收获了很多。（当然这个任务还没有结束就是了。）首先就是对go语言的熟悉程度上升了，这个真的很重要，虽然我之前一直在想找机会学习go，但每次开始却又被各种事情耽搁，这次刚好就强迫我来面对，让我没有了逃避的理由，真真正正静下来看一看go的语法，真的很感谢。第二个就是很久没有这种来回折腾的感觉了，这对我来说也是一种很好的放松，尤其是在我算法越学越迷茫，有点不知所措的时候。第三个就是这个过程中还是关于一些规范的东西进行了学习，包括就是github传issue以及编译的过程的学习。最后一点就是在这个过程中我好像又看到了某种希望，开始对编程，以及linux的学习又产生了很浓烈的兴趣。希望之后的我可以独立的将自己的想法通过编程来实现，这是最好的。

发表于   |   分类于 c语言   |   暂无评论

二分图 当且仅当图中不含奇数环。
二分图就是将图中的点分成左右两个集合，每条边都在两个集合之间
染色法判断是不是二分图
思路：利用dfs将每个点进行染色，将某个点染成白色，则以这个点为中心的其他点染成黑色，用1表示白色，用2表示黑色，0表示没有染过色，可以建立一个数组color[]，来存储染色情况，每次dfs先判断是否染色，如果没有就染成和上一个点不一样的颜色，可以用3去减，表示相反的颜色，如果有则判断是不是和上一点的颜色一样，如果一样就是有矛盾，表示出现了奇数环，则返回false，否则返回true。（给dfs传入的参数有两个一个是点，一个是染的颜色，可以设置一个默认值，默认传1）数据结构用邻接表来存图。因为每个点可能不会都是连通的，所以要遍历每一个点，判断是否染色，如果染过则跳过，如果没有则进行一遍dfs。为了判断最后的结构，我们需要一个判断的表示，所以可以新建一个布尔变量，一开始设置为true，之后如果某一次dfs返回值为false则将其设置为false，然后跳出循环。当循环结束之后只要判断这个布尔变量是否为true，为true则说明染色过程很顺利，该图是二分图，否则就不是二分图。
例题：

染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围1≤n,m≤1e5
输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

需要注意的是因为存的是无向图，所以边的数量应该是两倍于给的数量（相当于存两个方向相反的有向边）

匈牙利算法求二分图中最大的匹配数
思路：题目会给出一个二分图，先是遍历左边的点，每次遍历都遍历一遍那个点所连的边，让其和右边的点看能不能匹配，如果能那就匹配，如果不能就看一下那个被匹配的点于其匹配的那个点还有没有其他边的点可以与之匹配，如果可以，那就让那个点去匹配其他点，然后让现在这个点和被匹配的点匹配。去匹配其他点的过程是一个迭代的过程。数据结构是用的邻接表来存。对于手写邻接表中e[] , ne[] 的大小，应该是边的大小，因为每一个h都可以引出至多m（边数）条边，就是至多存有m个相连的点。定义一个bool st[]，表示被考虑过，每次遍历都要清空一下，表示在后面的迭代过程不会出现重复考虑的情况。定义一个int match[] , 用来存的是被匹配的点去匹配他的点。每次匹配成功就往答案中+1，当循环遍历完之后得到的就是最大匹配数。

例题：

二分图的最大匹配

给定一个二分图，其中左半部包含 n1 个点（编号1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
输入格式
第一行包含三个整数 n1、 n2和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围 1≤n1 , n2≤500 , 1≤u≤n1 1≤v≤n2 , 1≤m≤1e5
输入样例：

2 2 4
1 1
1 2
2 1
2 2

输出样例：

2

思路：虽然没有说是有向图还是无向图，但是根据匈牙利算法的实现方式，可以当作单向图去存，且必须是去匹配的集合作为去指向的一方。

//find()函数
bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

发表于   |   分类于 c语言   |   暂无评论

朴素prim（普利姆）算法
一般用这个算法解决稠密图，用邻接矩阵来存图。是无向边所以就是存两条反向的单向边，来表示。
思路和dijkstra算法差不多。
开一个n次遍历，每次遍历都从还没加到集合中的点选一个到集合距离最小的点，dijkstra算法求的是最短路，所以是到原点，prim算法是求一个所有边都是最小的树，即最小生成树，用集合来维持这个树，所以是到集合距离最小的点。
到集合的距离就是说每个点到这个集合中的某一个点的边。之后要求最小生成树一般不是把树给输出而是将其边的合输出。所以要有一个变量去存。一般存的时候先是判断是不是为第一次，因为第一次就是起点，其到集合的距离为0，之后在更新之前存。因为如果存在自环且权重为负，或者权重比本身到集合的距离小，那么在更新之后可能会有disk[t] = d[t] [t] 的这种情况，然后disk[t]的值就会发生变化，所以为了避免这种情况，一般都是将加入答案的操作放在更新之前。
判断有没有最小生成树，一开始将每一个点的距离初始化为无穷，如果就是在某一次遍历（除了第一次）中取得的点的距离为无穷，就是说明当前集合之外的点离集合最短的距离为无穷，也就是集合中没有一个点有和剩余的点向连的边，所以这个图就没有最小生成树。

例题：

Prim求最小生成树

给定一个 n个点 m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 VV 表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由 V中的全部 n个顶点和 E中 n−1 条边构成的无向连通子图被称为 G的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。
输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含三个整数u,v,w，表示点 u和点 v之间存在一条权值为 w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围 1≤n≤500, 1≤m≤105, 图中涉及边的边权的绝对值均不超过10000。
输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

kruskal（克鲁斯卡尔） 算法
利用到并查集的思想。基本思路就是先将每条边按照权重排序，然后维持一个集合，之后枚举每条边，假设枚举到的边的两个点不连通就将他们连起来，就是放到一个集合中，然后将权重加到答案中（因为从小到大枚举边，所以假设存在树结构，那么每条边一定是最小的，也就是实际上构成了最小生成树）。在存储边的时候因为只要能够排序就行，所以可以用结构体来存。
为了在排序的时候实现根据权重来排序，需要重载一下小于号
对于并查集在使用的时候需要初始化每个点的父节点为本身

bool operator < (const edge &W)const
{
    return w < W.w;
}

为了判断是否存在最小生成树，可以再新建一个变量cot，表示集合中的边数，当进行一次连通操作时（也就是并集）cot++，之后如果在所有边都枚举完之后，cot < n - 1 说明有点没有加入集合（一共 n 个点，应该一共 n - 1条边）那么就不存在最小生成树，反之等于 n - 1 时就存在，然后输出res
例题：

Kruskal求最小生成树

给定一个 n个点 m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 VV 表示图中点的集合，EE 表示图中边的集合，n=|V|，m=|E|。
由 V中的全部 n个顶点和 E中 n−1 条边构成的无向连通子图被称为 G的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。
输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含三个整数u,v,w，表示点 u和点 v之间存在一条权值为 w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围 1≤n≤105 , 1≤m≤2∗1e5 , 图中涉及边的边权的绝对值均不超过 1000。
输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6