Templates for XCPC - 图论（一）

二分图最大匹配

```
## 链式前向星+堆优化dijkstra
```cpp
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;
}

SPFA找负环

queue<int> Q;
int in_queue[N],cnt[N];
bool spfa(){
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        in_queue[u]=0;
        for(int i=frm[u];i;i=nxt[i]){
            if(dis[to[i]]>dis[u]+val[i]){
                dis[to[i]]=dis[u]+val[i];
                if(!in_queue[to[i]]){
                    Q.push(to[i]);
                    in_queue[to[i]]=1;
                    cnt[to[i]]++;
                    if(cnt[to[i]]>n)return true;
                }
            }
        }
    }
    return false;
}
int main(){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        cnt[i]=0;
    }
    dis[1]=0;
    Q.push(1);
    in_queue[1]=1;
    if(spfa())printf("存在负环");
    else printf("不存在负环");
    return 0;
}