2023烟台7天编程集训笔记4

//匈牙利算法代码 
//匈牙利算法可用邻接矩阵和编表，优化用编表，不优化用邻接矩阵
//时间复杂度：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代码，能找出图中的强连通分量
#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;
}