算法竞赛模板

链式前向星+堆优化dijkstra

void add_edge(int u,int v,int w){
	to[++_]=v;
	nxt[_]=frm[u];
	frm[u]=_;
	val[_]=w;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
int vis[N],dis[N];
void dijkstra(){
	while(!Q.empty()){
		int u=Q.top().second;
		Q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=frm[u];i;i=nxt[i]){
			if(dis[to[i]]>dis[u]+val[i]){
				dis[to[i]]=dis[u]+val[i];
				Q.push(make_pair(dis[to[i]],to[i]));
			}
		}
	}
}
int main(){
	for(int i=1;i<=n;i++){
		dis[i]=INF;
	}
	dis[1]=0;
	Q.push(make_pair(0,1));
	dijkstra();
	return 0;
}

EK 最大流

bool bfs(){
    memset(vis,0,sizeof(vis));
    memset(flow,0x3f,sizeof(flow));
    bool ret=0;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=frm[u];i;i=nxt[i]){
            int v=to[i],w=val[i];
            if(val[i]<=0||vis[v])continue;
            flow[v]=min(flow[u],w);
            pre[v]=i;
            vis[v]=1;
            Q.push(v);
            if(v==t)ret=1;
        }
    }
    return ret;
}
void update(){
    for(int i=t;i!=s;i=to[pre[i]^1]){
		val[pre[i]]-=flow[t];
		val[pre[i]^1]+=flow[t];
	}
}