ACM

图论

图论

[TOC]

最短路问题

  • 单源

    • 边权保证非负
      • 稠密图 - 朴素Dijkstra - O(n^2) - 找最短的点，利用它更新
      • 稀疏图 - 堆优化Dijkstra - O(mlogn) - 找最短的点，利用它更新
    • 存在负权边
      • 有边数限制 - Bellman-Ford - O(nm) - 结构体存，遍历k次所有边
      • 无边数限制 - SPFA - 一般O(m)，最坏O(nm) - 用被更新的点尝试更新其他点

  • 多源

    • Floyd - O(n^3) - 三层循环

朴素Dijkstra

#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int INF=0x3f3f3f3f;
int g[N][N],dis[N];
int n,m;
bool st[N];
void dijkstra(int s,int t){
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    for(int i=1;i<=n;i++){
        int idx=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]){
                if(idx==-1||dis[j]<dis[idx]){
                    idx=j;
                }
            }
        }
        if(idx==t)break;
        st[idx]=1;
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[idx]+g[idx][j],dis[j]);
        }
    }
    if(dis[t]==0x3f3f3f3f)cout<<"-1";
    else cout<<dis[t];
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);
    }
    dijkstra(1,n);
    return 0;
}

堆优化Dijkstra

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
typedef pair<int,int> PII;
int h[N],e[N],ne[N],w[N],idx,dist[N],n;
bool st[N];
priority_queue<PII,vector<PII>,greater<PII> >q;
void add(int a,int b,int c){
	w[idx]=c;
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
int dijkstra(void){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	q.push({0,1});
	while(!q.empty()){
		auto t=q.top();
		q.pop();
		int dis=t.first,id=t.second;
		if(id==n)break;
		if(st[id])continue;
		st[id]=1;
		for(int i=h[id];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dis+w[i]){
				dist[j]=dis+w[i];
				q.push({dist[j],j});
			}
		}
	}
	if(dist[n]==0x3f3f3f3f)return -1;
	else return dist[n];
}
int main(){
	int m,x,y,z;
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	cout<<dijkstra();
	return 0;
}

Bellman-Ford

注意if(d[n]>0x3f3f3f3f/2)printf("impossible");

#include<bits/stdc++.h>
using namespace std;
const int M=100010,N=510;
int n,m,k,backup[N],d[N];
struct node{
	int a,b,w;
}e[M];
void bellman_ford(void){
	memset(d,0x3f,sizeof d);
	d[1]=0;
	for(int i=0;i<k;i++){
		memcpy(backup,d,sizeof d);
		for(int j=0;j<m;j++){
			d[e[j].b]=min(d[e[j].b],backup[e[j].a]+e[j].w);
		}
	}
	if(d[n]>0x3f3f3f3f/2)printf("impossible");
	else printf("%d",d[n]);
}
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		cin>>e[i].a>>e[i].b>>e[i].w;
	}
	bellman_ford();
	return 0;
}

SPFA

可看作对Bellman-Ford的优化

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
queue<int>q;
int e[N],ne[N],h[N],w[N],idx,d[N],n,m;
bool st[N];
void add(int a,int b,int c){
	w[idx]=c;
	ne[idx]=h[a];
	e[idx]=b;
	h[a]=idx++;
}
void spfa(void){
	memset(d,0x3f,sizeof d);
	d[1]=0;
	q.push(1);
	st[1]=1;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(d[j]>d[t]+w[i]){
				d[j]=d[t]+w[i];
				if(!st[j]){
					q.push(j);
					st[j]=1;
				}
			}
		}
	}	
	if(d[n]==0x3f3f3f3f)printf("impossible");
	else printf("%d",d[n]);
}
int main(){
	cin>>n>>m;
	int x,y,z;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	spfa();
	return 0;
}

SPFA判断负环

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
queue<int>q;
int e[N],ne[N],h[N],w[N],idx,d[N],n,m,cnt[N];
bool st[N];
void add(int a,int b,int c){
	w[idx]=c;
	ne[idx]=h[a];
	e[idx]=b;
	h[a]=idx++;
}
bool spfa(void){
	memset(d,0x3f,sizeof d);
	d[1]=0;
	for(int i=1;i<=n;i++){
	    st[i]=1;
	    q.push(i);
	}
	while(!q.empty()){
		int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=e[i];
			if(d[j]>d[t]+w[i]){
				d[j]=d[t]+w[i];
				cnt[j]=cnt[t]+1;
				if(cnt[j]>=n)return true;
				if(!st[j]){
					q.push(j);
					st[j]=1;
				}
			}
		}
	}	
	return false;
}
int main(){
	cin>>n>>m;
	int x,y,z;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	if(spfa()){
		printf("Yes");
	}
	else printf("No");
	return 0;
}

Floyd

注意if(d[l][r]>INF/2)printf("impossible\n");

#include<bits/stdc++.h>
using namespace std;
const int N=210,INF=1e9;
int d[N][N];
int main(){
	int n,m,q,x,y,z;
	cin>>n>>m>>q;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==j)d[i][j]=0;
			else d[i][j]=INF;
		}
	}
	while(m--){
		cin>>x>>y>>z;
		d[x][y]=min(d[x][y],z);
	}
	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 l,r;
	while(q--){
		cin>>l>>r;
		if(d[l][r]>INF/2)printf("impossible\n");
		else cout<<d[l][r]<<endl;
	}
	return 0;
}

最小生成树

  • 稠密图 - Prim - O(n^2) - 每次将离连通部分的最近的点和点对应的边加入的连通部分
  • 稀疏图 - Kruskal - O(mlogm) - 边权从小到大，不形成回路就加入

Prim

#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N],d[N];
bool st[N];
int n,m,q,x,y,z;
void prim(void){
	int res=0;
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||d[t]>d[j])){
				t=j;
			}
		}
		
		if(i&&d[t]==INF){
			printf("impossible");
			return;
		}
		if(i){
			res+=d[t];
		}
		st[t]=1;
		for(int j=1;j<=n;j++){
			d[j]=min(d[j],g[t][j]);
		}
	}
	printf("%d",res);
}
int main(void){
	
	cin>>n>>m;
	memset(d,0x3f,sizeof d);
	memset(g,0x3f,sizeof g);
	while(m--){
		cin>>x>>y>>z;
		g[x][y]=g[y][x]=min(g[x][y],z);
	}
	prim();
	return 0;
}

Kruskal

#include<bits/stdc++.h>
using namespace std;
const int M=200010;
int p[M];
struct node{
	int a,b,w;
	bool operator<(const node &W)const{
		return w<W.w;
	}
}e[M];
int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	
	for(int i=0;i<m;i++){	
	    int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		e[i]={a,b,w};
	}
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	sort(e,e+m);
	int cnt=0,res=0;
	for(int i=0;i<=m;i++){
		int aa=e[i].a,bb=e[i].b,ww=e[i].w;
		aa=find(aa),bb=find(bb);
		if(aa!=bb){
			res+=ww;
			p[aa]=bb;
			cnt++;
		}
	}
	if(cnt<n-1)printf("impossible");
	else printf("%d\n",res);
	return 0;
}

二分图

染色法判定二分图

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
queue<int>q;
int e[2*N],ne[2*N],h[N],idx,st[N],ans=1;
void add(int x,int y){
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}
bool dfs(int t,int k){
	st[t]=k;
	for(int i=h[t];i!=-1;i=ne[i]){
		int j=e[i];
		if(!st[j]){
		    if(!dfs(j,3-k)){
		        return false;
		    }
		}
		else if(st[j]==k){
		    return false;
		}
	}
	return true;
}
int main(){
    int n,m,u,v;
    scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    bool flag=true;
    for(int i=1;i<=n;i++){
    	if(!st[i]){
    	    if(!dfs(i,1)){
    	        flag=false;
    	        break;
    	    }
    	}
	}
    if(flag){
    	cout<<"Yes";
	}
	else{
		cout<<"No";
	}
    return 0;
}

匈牙利算法-二分图的最大匹配

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
bool st[N];
int match[N];
void add(int x,int y){
	e[idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
}
bool find(int k){
	for(int i=h[k];i!=-1;i=ne[i]){
		int j=e[i];
		if(!st[j]){
			st[j]=true;
			if(match[j]==0||find(match[j])){
				match[j]=k;
				return true;
			}
		}
			
	}
	return false;
} 
int main(){
	int n1,n2,m,u,v;
	memset(h,-1,sizeof h);
	scanf("%d%d%d",&n1,&n2,&m);
	while(m--){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	int res=0;
	for(int i=1;i<=n1;i++){
		memset(st,0,sizeof st);
		if(find(i))res++;
	}
	printf("%d",res);
	return 0;
}