最短路Dijkstra，spfa，图论二分图算法AYIT---ACM训练(模板版)

向右看齐 2024-04-24 23:18 80阅读 0赞

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]  
![在这里插入图片描述][24f5ac9881e3400d837df92b329ca125.png]

#### 文章目录 ####

*  前言
 *  A - Dijkstra Algorithm
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  B - 最长路
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  C - 二分图最大匹配
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  D - 搭配飞行员
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  E - The Perfect Stall
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  F - Asteroids
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  G - Til the Cows Come Home
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  H - 拓扑排序
 *   *  0x00 算法题目
     *  0x01 算法思路
     *  0x02 代码实现
 *  总结

--------------------

## 前言 ##

最短路Dijkstra，spfa，图论二分图算法AYIT—ACM训练(模板版)  
A — Dijkstra  
B — spfa/Dijkstra  
C — 二分图  
D — 二分图  
E — 二分图  
F — 二分图  
G — Dijkstra  
H — Topsort

--------------------

## A - Dijkstra Algorithm ##

### 0x00 算法题目 ###

![在这里插入图片描述][34a3a3c5161642a096e440eb7daefdb1.png]

### 0x01 算法思路 ###

**Dijkstra算法基础模板题**

? 模板演示：

int dijkstra()
    {
        
        memset(dist,0x3f,sizeof dist);
    
        dist[1]=0;
    
        for(int i=0;i<n;i++)
        {
        
            int t=-1;
            for(int j=1;j<=n;j++)
            {
        
                if(!st[j] && (t==-1 || dist[t] > dist[j]))
                    t=j;
            }
    
            st[t]=true;
    
            for(int j=1;j<=n;j++)
                dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        if(dist[n]==0x3f3f3f3f) return -1;
        return dist[n];
    
    }

### 0x02 代码实现 ###

**朴素版本Dijkstra：**

? 代码演示：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    const int N = 510;
    int g[N][N];
    bool st[N];
    int dist[N];
    int n,s,f;
    
    int dijkstra()
    {
        
    	memset(dist,0x3f,sizeof dist);
    	dist[s]=0;
    	
    	for(int i=0;i<n;i++)
    	{
        
    		int t=-1;
    		for(int j=1;j<=n;j++)
    			if(!st[j] && (t==-1 || dist[t] > dist[j]))
    				t=j;
    		
    		st[t]=true;
    		for(int j=1;j<=n;j++)
    			dist[j]=min(dist[j],dist[t]+g[t][j]);
    	}
    	if(dist[f]==0x3f3f3f3f) return -1;
    	return dist[f];
    }
    
    int main()
    {
        
    	cin>>n>>s>>f;
    	
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=n;j++)
    		{
        
    			int x;
    			cin>>x;
    			if(x==-1) g[i][j]=0x3f3f3f3f;
    			else g[i][j]=x;
    		}
    	}
    	
    	int t =dijkstra();
    	cout<<t<<endl;
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]  
**spfa算法：**  
? 代码演示：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    
    using namespace std;
    const int N=110,M=110*110;
    int n,s,f;
    bool st[N];
    int h[N],w[M],ne[M],e[M],idx;
    int dist[N];
    
    void add(int a,int b,int c)
    {
        
    	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    }
    
    int spfa()
    {
        
    	memset(dist,0x3f,sizeof dist);
    	dist[s]=0;
    	queue<int> q;
    	q.push(s);
    	while(q.size())
    	{
        
    		int t = q.front();
    		q.pop();
    		st[t]=false;
    		
    		for(int i=h[t];i!=-1;i=ne[i])
    		{
        
    			int j=e[i];
    			if(dist[j] > dist[t] + w[i])
    			{
        
    				dist[j]=dist[t]+w[i];
    				if(!st[j])
    				{
        
    					q.push(j);
    					st[j]=true;
    				}
    			}
    		}
    	}
    	if(dist[f]==0x3f3f3f3f) return -1;
    	else return dist[f];
    }
    
    int main()
    {
        
    	cin>>n>>s>>f;
    	memset(h,-1,sizeof h);
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=n;j++)
    		{
        
    			int x;
    			cin>>x;
    			//if(x==-1) continue;
    			if(x>0) add(i,j,x);
    		}
    	}
    	cout<<spfa()<<endl;
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## B - 最长路 ##

### 0x00 算法题目 ###

![在这里插入图片描述][f91693533e7d4cb7aeeee4d1b3542495.png]

### 0x01 算法思路 ###

**spfa算法基础模板题**

? 模板演示：

int spfa()
    {
        
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        queue<int> q;
        q.push(1);
    
        while(q.size())
        {
        
            auto t = q.front();
            q.pop();
            st[t]=false;
            for(int i=h[t];i!=-1;i=ne[i])
            {
        
                int j = e[i];
                if(dist[j] > dist[t]+w[i])
                {
        
                    dist[j]=dist[t]+w[i];
                    if(!st[j])
                    {
        
                        q.push(j);
                        st[j]=true;
                    }
                }
            }
        }
        return dist[n];
    }

### 0x02 代码实现 ###

**spfa算法：**  
? 代码演示：

#include<bits/stdc++.h>
    #define endl '\n'
    
    using namespace std;
    const int N = 1510,INF = 0x3f3f3f3f;
    int n,m;
    int dist[N];
    int g[N][N];
    queue<int> q;
    
    void spfa()
    {
        
    	memset(dist,-1,sizeof dist);
    	dist[1]=0;
    	q.push(1);
    	while(!q.empty())
    	{
        
    		int t = q.front();
    		q.pop();
    		for(int j=1;j<=n;j++)
    		{
        
    			if(g[t][j] && dist[j] < dist[t] + g[t][j])
    			{
        
    				dist[j] = dist[t] + g[t][j];
    				q.push(j);
    			}
    		}
    	}
    	
    }
    
    int main()
    {
        
    	cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{
        
    		int a,b,c;
    		cin>>a>>b>>c;
    		g[a][b]=max(g[a][b],c);
    	}
    	spfa();
    	cout<<dist[n]<<endl;
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## C - 二分图最大匹配 ##

### 0x00 算法题目 ###

![在这里插入图片描述][799ae08dad5b41728f66194da39b76d4.png]

### 0x01 算法思路 ###

**二分图模板题**

? 模板演示：

//邻接表
    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] == 0 || find(match[j]))
                {
        
                    match[j] = x;
                    return true;
                }
            }
        }
    
        return false;
    }
    //邻接矩阵
    bool find(int x)
    {
        
        for(int i=0;i<g[x].size();++i)
        {
        
            int j = g[x][i];
            if(!st[j])
            {
        
                st[j]=true;
                if(match[j]==0 || find(match[j]))
                {
        
                    match[j]=x;
                    return true;
                }
            }
        }
        return false;
    }

### 0x02 代码实现 ###

? 代码演示：

#include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N = 510,M=5e4+10;
    int n,m,q;
    int h[N],e[M],ne[M],idx;
    int match[N];
    bool st[N];
    
    void add(int a,int b)
    {
        
    	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    
    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]==0 || find(match[j]))
    			{
        
    				match[j]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    int main()
    {
        
    	cin>>n>>m>>q;
    	memset(h,-1,sizeof h);
    	while(q--)
    	{
        
    		int u,v;
    		cin>>u>>v;
    		add(u,v);
    	}
    	int res=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		memset(st,false,sizeof st);
    		if(find(i)) res++;
    	}
    	cout<<res<<endl;
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## D - 搭配飞行员 ##

### 0x00 算法题目 ###

![在这里插入图片描述][cbb1c8886d3244ee9cd7e7b168a7d5fd.png]

### 0x01 算法思路 ###

**二分图模板题**

? 模板演示：

### 0x02 代码实现 ###

? 代码演示：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<bits/stdc++.h>
    
    using namespace std;
    const int N = 110;
    
    int n,m;
    int map[N][N];
    int match[N];
    bool st[N];
    vector<int> g[N];
    bool find(int x)
    {
        
    	for(int i=0;i<g[x].size();++i)
    	{
        
    		int j = g[x][i];
    		if(!st[j])
    		{
        
    			st[j]=true;
    			if(match[j]==0 || find(match[j]))
    			{
        
    				match[j]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    int main()
    {
        
    	scanf("%d %d",&n,&m);
    	int a,b;
    	while(cin>>a>>b)
    	{
        
    		g[a].push_back(b);
    	}
    	
    	int res = 0;
    	for(int i=1;i<=m;i++)
    	{
        
    		memset(st,false,sizeof st);
    		if(find(i)) 
    		{
        
    			res++;
    		}
    	}
    	
    	cout<<res;
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## E - The Perfect Stall ##

### 0x00 算法题目 ###

![在这里插入图片描述][c1c794150418498da44c43fdbffc6729.png]

### 0x01 算法思路 ###

**二分图模板题**

? 模板演示：

### 0x02 代码实现 ###

? 代码演示：

#include<algorithm>
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 510,M=5e4+10;
    int n,m;
    int match[N];
    bool st[N];
    vector<int> g[N];
    
    bool find(int x)
    {
        
    	for(int i=0;i<g[x].size();++i)
    	{
        
    		int j = g[x][i];
    		if(!st[j])
    		{
        
    			st[j]=true;
    			if(match[j]==0 || find(match[j]))
    			{
        
    				match[j]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    int main()
    {
        
    	while(~scanf("%d%d",&n,&m))
    	{
        
    		memset(st,false,sizeof st);
    		memset(match,0,sizeof match);
    		for(int i=1;i<=n;i++)
    		{
        
    			
    			g[i].clear();
    			int s;
    			cin>>s;
    			while(s--)
    			{
        
    				int q;
    				cin>>q;
    				g[i].push_back(q);
    			}
    		}
    		int res=0;
    		for(int i=1;i<=n;i++)
    		{
        
    			memset(st,false,sizeof st);
    			if(find(i)) res++;
    		}
    		cout<<res<<endl;
    	}
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## F - Asteroids ##

### 0x00 算法题目 ###

![在这里插入图片描述][c5ae229c34bb4e18a3abcfbe3b571320.png]

### 0x01 算法思路 ###

**二分图模板题**

? 模板演示：

### 0x02 代码实现 ###

? 代码演示：

#include<iostream>
    #include<cstring>
    using namespace std;
    const int N = 510,M=5e4+10;
    int n,m,q;
    int h[N],e[M],ne[M],idx;
    int match[N];
    bool st[N];
    
    void add(int a,int b)
    {
        
    	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    
    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]==0 || find(match[j]))
    			{
        
    				match[j]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    int main()
    {
        
    	cin>>n>>m;
    	memset(h,-1,sizeof h);
    	while(m--)
    	{
        
    		int u,v;
    		cin>>u>>v;
    		add(u,v);
    	}
    	int res=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		memset(st,false,sizeof st);
    		if(find(i)) res++;
    	}
    	cout<<res<<endl;
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## G - Til the Cows Come Home ##

### 0x00 算法题目 ###

![在这里插入图片描述][db4dc1b5bece4119b47aa786fa80dabd.png]

### 0x01 算法思路 ###

**Dijkstra算法基础模板题**

? 模板演示：

### 0x02 代码实现 ###

? 代码演示：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<stdbool.h>
    
    using namespace std;
    
    const int N=1010,inf = 0x3f3f3f3f;
    
    int n,m;
    bool st[N];
    int dist[N];
    int g[N][N];
    
    int dijkstra()
    {
        
    	memset(dist,inf,sizeof(dist));
    	dist[1]= 0;
    	for(int i=1;i <= n;i++)
    	{
        
    		int t=-1;
    		for(int j=1;j<=n;j++)
    			if(!st[j] && (t==-1 || dist[t] > dist[j]))
    				t=j;
    		
    		st[t]=true;
    		for(int j=1;j<=n;j++)
    			dist[j]=min(dist[j],dist[t]+g[t][j]);
    	}
    	return dist[n];
    }
    
    
    int main()
    {
        
    	cin>>m>>n;
    	memset(g,inf,sizeof g);
    	
    	for(int i=0;i<m;++i)
    	{
        
    		int a,b,c;
    		cin>>a>>b>>c; 
    		g[a][b]=g[b][a]=min(g[a][b],c);
    	}
    	cout<< dijkstra() <<endl;
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

## H - 拓扑排序 ##

### 0x00 算法题目 ###

![在这里插入图片描述][6354d7c6907849a9a89986553b7eb16a.png]

### 0x01 算法思路 ###

**拓扑排序算法基础模板题**

? 模板演示：

bool topsort()
    {
        
        int hh=0,tt=-1;
    
        for (int i = 1; i <= n; i ++ )
            if (!d[i])
                q[ ++ tt] = i;
    
        while(hh<=tt)
        {
        
            int t = q[hh ++ ];
    
            for (int i = h[t]; i != -1; i = ne[i])
            {
        
                int j = e[i];
                if (-- d[j] == 0)
                    q[ ++ tt] = j;
            }
        }
        return tt==n-1;
    }

### 0x02 代码实现 ###

? 代码演示：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<vector>
    
    using namespace std;
    
    const int N=100010;
    
    int n,m;
    vector<int> v[N];
    int size,d[N];
    int ans[N];
    
    void topsort()
    {
        
    	priority_queue<int,vector<int>,greater<int> > q;
    	for(int i=1;i<=n;i++)
    		if(!d[i]) q.push(i);
    	
    	while(!q.empty())
    	{
        
    		int t = q.top();
    		q.pop();
    		ans[size++] = t;
    		for(auto it : v[t])
    		{
        
    			d[it]--;
    			if(!d[it]) q.push(it);
    		}
    	}
    }
    
    int main()
    {
        
    	cin>>n>>m;
    	
    	for(int i=0;i<m;i++)
    	{
        
    		int a,b;
    		cin>>a>>b;
    		v[a].push_back(b);
    		d[b]++;
    	}
    	topsort();
    	
    	for(int i=0 ; i<size ;i++)
    		cout<< 'v' << ans[i] <<' ';
    	
    	return 0;
    }

? 运行结果：  
![在这里插入图片描述][fbd8c372fee0460eab10d9f0964d7c16.png]

--------------------

## 总结 ##

**这次训练很明显涉及到了最短路Dijkstra，spfa，图论二分图算法，以及topsort算法，这次考的比较基础，但是让我意识到了，算法必须熟练记忆模板是很重要的。**

[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/31364eea2ad640368ca7cc5b3defea1f.gif
[24f5ac9881e3400d837df92b329ca125.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/d39979eafa3943ba90cdaba774a1ffc8.png
[34a3a3c5161642a096e440eb7daefdb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/047e4eb09007446da2998f730f322ee3.png
[fbd8c372fee0460eab10d9f0964d7c16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/fd95d79ddbcc42d28eb46fde0cbbe177.png
[f91693533e7d4cb7aeeee4d1b3542495.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/186b5e12544f4676852a14fd2a2ecf44.png
[799ae08dad5b41728f66194da39b76d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/06b7d5d9b5df4937b5608e1afa2d61a4.png
[cbb1c8886d3244ee9cd7e7b168a7d5fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/60d604ddf6924a50b2a2bdb9e11e5bd2.png
[c1c794150418498da44c43fdbffc6729.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/e381d54ce1494ac4b9d3af0fa0400848.png
[c5ae229c34bb4e18a3abcfbe3b571320.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/8bc8753c073643bdb5f18bdcdbb8ecfe.png
[db4dc1b5bece4119b47aa786fa80dabd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/32d006c44b114ec596c24037cab15994.png
[6354d7c6907849a9a89986553b7eb16a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/12cf5c2b4a434472a0f3a8b411a73a58.png