图论:二部图
二部(分)图
定义: 二部图是一种特殊的图,可以将图的节点分为2个几个,且每个集合中,节点之间没有关联。大概长这个样子:
理论判断:
- 图 G 中至少存在两个点,且图中所有回路的长度均为偶数。
- 任何无回路的的图均是二分图。
判断图为二部图的方法:染色法
定义:对每一个顶点dfs,对本身染色为1,对其邻点染色成2,若存在其本身与其相邻的节点的颜色相同,则不是二分图,否则是二分图。
例题: AcWing 860. 染色法判定二分图
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+11;
vector<int>e[N];
int color[N];
bool dfs(int x,int c)
{
color[x]=c;
for(int i=0;i<e[x].size();i++)
{
int j=e[x][i];
if(!color[j])
{
if(!dfs(j,3-c))
return 0;
}
if(color[x]==color[j])
return 0;
}
return 1;
}
int main()
{
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(!color[i])
{
if(!dfs(i,1))
{
cout<<"No";
return 0;
}
}
}
cout<<"Yes";
return 0;
}
Something derived
-
最大匹配:给定二分图 G 中的所有匹配,所含匹配边数最多的匹配,称为这个图的最大匹配。如图:选择最大匹配的问题即为图的最大匹配问题
如图,红边就是一个最大匹配
-
完全匹配:一个匹配中,图中每个顶点都与图中某条边相关联,则称此匹配为完全匹配,即一个图的某个匹配中,所有的顶点都是匹配点,就是一个完全匹配。
显然,由于完全匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突,因此完全匹配一定是最大匹配。 -
完美匹配:对于一个二分图,左点集与右点集的点数相同,若存在一个匹配,包含左点集、右点集的所有顶点,则称为完美匹配
-
最优匹配:带权二分图的权值最大的完全匹配称为最佳匹配。
匈牙利算法:
匈牙利算法主要用来解决两个问题:求二分图的最大匹配数和最小点覆盖数。
首先说明2个概念交替路 和增广路:
- 交替路:交替路从一个未匹配点出发,依次经过 非匹配边、匹配边、非匹配边… 形成的路径
- 增广路:如果交替路经过除出发点外的另一个未匹配点,则这条交替路称为增广路)
如图: 8-4-7-1-5为一交替路; 8-4-7-1-5-2为一增广路
增广路的结论: - P的路径长度一定为奇数
- 对增广路径编号,所有奇数的边都不在M中,偶数边在M中
- P经过取反操作可以得到一个更大的匹配图,比原来匹配多一个
- 当且仅当不存在关于图M的增广路径,则图M为最大匹配
所以匈牙利算法的思路就是:不停找增广路,并增加匹配的个数
放个例题: 二分图的最大匹配
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+11;
int first[N];
struct node
{
int u,v,nxt;
}e[N];
int n1,n2,m;
int ans=0;
int vis[N];
int cp[N];
bool dfs(int x,int tag)
{
if(vis[x]==tag)
return 0;
vis[x]=tag;
for(int i=first[x];i!=-1;i=e[i].nxt)
{
int j=e[i].v;
if(!cp[j] || dfs(cp[j],tag))
{
cp[j]=x;
return 1;
}
}
return 0;
}
int main()
{
cin>>n1>>n2>>m;
int u,v;
memset(first,-1,sizeof(first));
for(int i=1;i<=m;i++)
{
cin>>u>>v;
e[i].u=u;
e[i].v=v;
e[i].nxt=first[u];
first[u]=i;
}
for(int i=1;i<=n1;i++)
{
if(dfs(i,i))
ans++;
}
cout<<ans;
return 0;
}
mood:雷神4挺好看的
dai _ tu: epoch 次数,网络的深和宽度,学习率;激活函数用prelu好一些
菜鸟变凤凰2023: 博主写得很好,文件名完全按照帖子中的来. 看了7,8篇贴子,只有这个敲完能运行起来.
菜鸟变凤凰2023: epoch 1次,正好相反; 10次大部分都是狗
大概改哪几个参数能提高准确率?
菜鸟变凤凰2023: 我用的25000条的那个官方的数据集,训练了10次,然后检测的时候也是大部分是狗, 只有3成的正确率
dai _ tu: 将epoch调大,神经网络里面的超参也改一下,提高准确率就行了