算法基础课-图论

图论

顺序add

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c;
	if(h[a]==-1||b<e[h[a]]) ne[idx]=h[a],h[a]=idx++;
	else
	{
		int t=h[a],pre=h[a];
		while(b>e[t]&&t!=-1)
			pre=t,t=ne[t];
		ne[idx]=t,ne[pre]=idx++;
	}
}

1.dfs

#include <iostream>
#include <cstring>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int n;
bool st[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}


int maxn=0;

int dfs(int u)
{
    st[u]=1;
    int res=0,sum=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(st[j]==0)
        {
            int s=dfs(j);
            sum+=s;
            res=max(res,s);
        }
    }
    res=max(res,n-sum);
    maxn=max(res,maxn);
    return sum;
    
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    cout<<dfs(1);
}

2.bfs

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(int u)
{
    queue<int>q;
    q.push(u);
    memset(d,-1,sizeof d);
    d[u]=0;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1)
            {
                d[j]=d[t]+1;
                q.push(j);
            }
        }
    }
    return d[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs(1);
}

3.拓扑排序

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int n,m;
int d[N];
vector<int>ans;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool Topo()
{
    queue<int>q;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
            q.push(i);
            cnt++;
            ans.push_back(i);
        }
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)
            {
                q.push(j);
                cnt++;
                ans.push_back(j);
            }
        }
    }
    if(cnt==n) return true;
    return false;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        d[y]++;
    }
    if(Topo())
    {
        int a=ans.size();
        for(int i=0;i<a;i++)
        cout<<ans[i]<<" ";
        cout<<endl;
    }
    else
    cout<<-1<<endl;
}

4.dijkstra1

#include <iostream>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=510;
int n,m;
int G[N][N];
int dist[N],st[N];

int dijkstra()
{
    memset(dist,INF,sizeof dist);
    dist[1]=0;
    for(int i=1;i<=n;i++)
    {
        int t=-1;//findMin
        for(int j=1;j<=n;j++)
        {
            if(!st[j] && (t==-1 ||dist[j]<dist[t]))
                t=j;
        }
        st[t]=1;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+G[t][j]);
    }
    if(dist[n]==INF) return -1;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(G,INF,sizeof G);
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        G[x][y]=min(G[x][y],z);
    }
    int ans=dijkstra();
    cout<<ans;
}

5.dijkstra2

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=2e5;
const int INF=0x3f3f3f3f;
int h[N],e[N],ne[N],w[N],idx;
int n,m;
int dist[N],st[N];
typedef pair<int,int>PII;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra()
{
    memset(dist,INF,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>pq;
    pq.push({0,1});
    while(!pq.empty())
    {
        auto t=pq.top();
        pq.pop();
        int ver=t.second;
        
        if(st[ver]) continue;
        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[ver]+w[i]<dist[j])
            {
                dist[j]=dist[ver]+w[i];
                pq.push({dist[j],j});
            }
        }
    }
    if(dist[n]==INF) return -1;
    else return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra();
}

6.floyd

#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=210;
const int M=2e4+10;
int n,m,k;
int d[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
        }
    }
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        d[x][y]=min(d[x][y],z);
    }
    floyd();
    for(int i=0;i<k;i++)
    {
        int x,y;
        cin>>x>>y;
        if(d[x][y]>INF/2) cout<<"impossible"<<endl;
        else cout<<d[x][y]<<endl;
    }
}

7.prim

#include <iostream>
#include <cstring>

using namespace std;
const int N=510;
const int M=1e5+10;
const int INF=0x3f3f3f3f;
int n,m;
int G[N][N],dist[N],st[N],pre[N];

int prim()
{
    memset(dist,INF, sizeof(dist));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dist[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }
        if(dist[t] == INF) return INF;
        st[t] = 1;// 选择该点
        res += dist[t];
        for(int j = 1; j <= n; j++)//更新生成树外的点到生成树的距离
        {
            if(dist[j] > G[t][j] && !st[j])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dist[j] = G[t][j];//更新距离
                pre[j] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }
    return res;
}
void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
}
int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i ==j) G[i][j] = 0;
            else G[i][j] = INF;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        G[a][b]=G[b][a]=min(G[a][b],c);
    }
    int t=prim();
    if(t==INF) cout<<"impossible";
    else cout<<t;
    getPath();

8.kruskal

#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+10;
const int INF=0x3f3f3f3f;
struct Edge
{
    int a,b,c;
}edges[N];

bool cmp(Edge a,Edge b)
{
    return a.c<b.c;
}
int Father[N];
int n,m;


void Make_set(int x)
{
    Father[x]=0;
}
int find(int x)
{
    if(Father[x]<=0) return x;
    Father[x]=find(Father[x]);
    return Father[x];
}
void Union(int a,int b)
{
    int fx=find(a),fy=find(b);
    if(fx==fy) return;
    if(Father[fx]<=Father[fy])
    {
        Father[fy]=fx;
    }
    else
    {
        Father[fx]=fy;
        if(fx==fy)
            Father[fy]--;
    }
}
int kruskal()
{
    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,c=edges[i].c;
        int fa=find(a),fb=find(b);
        if(fa!=fb)
        {
            res+=c;
            cnt++;
            Union(fa,fb);
        }
    }
    if(cnt==n-1) return res;
    else return INF;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) Make_set(0);
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        edges[i]={u,v,w};
    }
    sort(edges,edges+m,cmp);
    int t=kruskal();
    if(t==INF) cout<<"impossible";
    else cout<<t;
}

9.去火车站

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 20010;
const int INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
typedef pair<int, int>PII;
void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(int u,int dist[N],int st[N])
{
	memset(dist, INF, sizeof dist);
	for(int i=1;i<=3;i++) cout<<dist[i]<<" ";
	dist[u] = 0;
	priority_queue<PII, vector<PII>, greater<PII>>pq;
	pq.push({ 0,u });
	while (!pq.empty())
	{
		auto t = pq.top();
		pq.pop();
		int ver = t.second;
		if (st[ver]) continue;

		st[ver] = 1;
		for (int i = h[ver]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[ver] + w[i])
			{
				dist[j] = dist[ver] + w[i];
				pq.push({ dist[j],j });
			}
		}
	}

	cout << endl;
}
int main()
{
	int dist1[N], dist2[N], st1[N], st2[N];
	memset(dist1, INF, sizeof dist1);
	memset(dist2, INF, sizeof dist2);
	int n, s, t;
	cin >> n >> s >> t;
	int m;
	cin >> m;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	dijkstra(s, dist1, st1);
	dijkstra(t, dist2, st2);

	int k;
	cin >> k;
	int mint = INF;
	int flag = 0;
	for (int i = 0; i < k; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		if (dist1[x] + dist2[y] + z < mint)
		{
			mint = dist1[x] + dist2[y] + z;
			printf("dist1:%d  dist2:%d  z:%d\n",dist1[x],dist2[y],z);
			flag = 1;
		}
			
	}
	for (int i = 1; i <= n; i++)
	{
		if (dist1[i] + dist2[i] < mint)
			{
				mint = dist1[i] + dist2[i] ;
				printf("dist1:%d  dist2:%d\n",dist1[i],dist2[i]);
				flag = 0;
			}
	}
	cout << mint;
}

染色法二分图

#include <iostream>
#include <cstring>
using namespace std;

const int N=1e5+10;
const int M=2e5+10;
int h[N],e[M],ne[M],idx;
int color[N];

void add(int x,int y)
{
    e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}

bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c))
                return false;
        }
        else if(color[j]==c) 
            return false;
    }
    return true;
}
int main()
{
    memset(h,-1,sizeof h);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    int flag=1;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=0;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
}

匈牙利算法

#include <iostream>
#include <cstring>
using namespace std;

const int N=510;
const int M=1e5+10;
int h[N],e[M],ne[M],idx;
int match[N],st[N];//st是看女孩是否考虑过，match是看女孩匹配的男孩
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]=1;
            if(!match[j]||find(match[j]))
            {
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(h,-1,sizeof h);
    int n1,n2,m;
    cin>>n1>>n2>>m;
    int res=0;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n1;i++)//遍历每个男孩
    {
        memset(st,0,sizeof st);
        if(find(i)) res++;
    }
    cout<<res;
}