匈牙利算法
点击查看代码
//匈牙利算法代码
//匈牙利算法可用邻接矩阵和编表，优化用编表，不优化用邻接矩阵
//时间复杂度：O(n^3)
#include <bits/stdc++.h>
using namespace std;
bool z[maxn][maxn],vis[maxn];//z[i][j]代表左边第i个点和右边第j个点能不能匹配 vis[i]代表右边第i个点在这一轮中有没有被请求匹配过
int n,m,k,result[maxn],ans;//n：左边有n个点，m:右边有m个点，k：中间有r条边，result[i]代表右边第i个点和左边第result[i]个点匹配
bool dfs(int i)//让左边第i个点尝试匹配，返回是否成功
{
for(int j=1;j<=m;j++)//让左边的第i个点和右边第j个点尝试匹配
{
if(z[i][j]&&!vis[j])
{
vis[j]=true;
if(!result[j]||dfs(result[j]))
{
result[j]=i;
return true;
}
}
}
return false;
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
int p1,p2;
cin>>p1>>p2;
z[p1][p2]=true;
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans;
return 0;
}
匈牙利算法优化
点击查看代码
//匈牙利算法优化代码
//如需优化，要用编表
//时间复杂度：最坏是O(n*边数)
#include <bits/stdc++.h>
using namespace std;
vector<int> z[maxn];//z[i][j]代表左边第i个点和右边第j个点能不能匹配
bool vis[maxn];//vis[i]代表右边第i个点在这一轮中有没有被请求匹配过
int n,m,k,result[maxn],ans;//n：左边有n个点，m:右边有m个点,k：中间有k条边，result[i]代表右边第i个点和左边第result[i]个点匹配
void add_edge(int s,int e)
{
z[s].push_back(e);
}
bool dfs(int i)//让左边第i个点尝试匹配，返回是否成功
{
for(int k=0;k<z[i].size();k++)//让左边的第i个点和右边第j个点尝试匹配
{
int j=z[i][k];
if(!vis[j])
{
vis[j]=true;
if(!result[j]||dfs(result[j]))
{
result[j]=i;
return true;
}
}
}
return false;
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
int p1,p2;
cin>>p1>>p2;
add_edge(p1,p2);
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i)) ans++;
}
cout<<ans;
return 0;
}
强连通分量定义在有向图，找到点边使互相能走到就构成了一个强连通分量，独立的点也可以构成一个强连通分量，找强连通分量要找环
连到自己祖先的边叫回边，反之叫做横叉边，横叉边虽然不能组成环，但能扩大一个环
tarjan
点击查看代码
//tarjan代码，能找出图中的强连通分量
#include<bits/stdc++.h>
using namespace std;
vector<int> z[maxn];
void add_edge(int s,int e)
{
z[s].push_back(e);
}
int num,n,m;;//当前已经 DFS了num个点
int dfn[maxn];//dfn[i]第i个点是第几个被 DFS到的
int low[maxn];//low[i]代表从i点出发，沿着回边，树边or能扩大环的横叉边走能够走到的所有点中dfn最小的点（深度较小）
stack<int> s;//栈用来储存被DFS过，但还没有求出强连通分量的点
bool instack[maxn];//instack[i]代表i是否在栈里面
int cnt;//有几个强连通分量
int belong[maxn];//belong[i]表示i属于哪一个强连通分量
void dfs(int i)//当前搜索到了i点
{
num++;
dfn[i]=low[i]=num;
s.push(i);
instack[i]=true;
for(int k=0;k<z[i].size();k++)
{
int j=z[i][k];
if(!dfn[j])//这是一条树边
{
dfs(j);
low[i]=min(low[i],low[j]);
}
else//非树边，这是一条回边or能扩大环的横叉边
{
if(instack[j])
{
low[i]=min(low[i],dfn[j]);//if(instack[j])low[i]=min(low[i],low[j]); 两种写法都可以
}
}
}
if(dfn[i]==low[i])
{
cnt++;//多了一个强连通分量
while(s.top()!=i)
{
belong[s.top()]=cnt;
instack[s.top()]=false;
s.pop();
}
s.pop();
instack[i]=false;
belong[i]=cnt;
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int p1,p2;
cin>>p1>>p2;
add_edge(p1,p2);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
dfs(i);
}
}
return 0;
}