Skip to content

Latest commit

 

History

History
1332 lines (1119 loc) · 33.3 KB

5-图论.md

File metadata and controls

1332 lines (1119 loc) · 33.3 KB
Raw

5-图论

最短路

dijkstra

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 10+1e5;
const ll inf = 0x3f3f3f3f;
typedef pair<ll,ll> pll;
    vector<pll> mp[100100];
    ll n,m,s;
    ll dis[100100];
    ll vis[100100];

void dij(ll s){
    for(ll i=1;i<=n;i++){
        dis[i]=inf;
    }
    dis[s]=0;
    priority_queue<pll,vector<pll>,greater<pll> > q;
    q.push({dis[s],s});
    while(!q.empty()){
        ll u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto [w,v]:mp[u]){
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int main() {
	cin>>n>>m>>s;
	for(ll i=1;i<=m;i++){
    	ll u,v,w;
    	cin>>u>>v>>w;
    	mp[u].push_back({w,v});
	}
	dij(s);
	for(ll i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}

并查集

已移至数据结构部分

最小生成树

prim O(n^2)

    vector<pll> edge[maxn];
    ll dis[maxn];
    ll vis[maxn];
void update(ll u){
    for(auto [v,w]:edge[u]){
        dis[v]=min(dis[v],w);
    }

}
ll prim(ll n){
    for(ll i=1;i<=n;i++){
        vis[i]=0;
        dis[i]=inf;
    }
    vis[1]=1;
    update(1);
    ll ans=0;
    for(ll i=1;i<=n-1;i++){//连接n-1条边
        ll pos,mi=inf;
        for(ll j=1;j<=n;j++){
            if(vis[j]) continue;
            if(dis[j]<mi){
                mi=dis[j];
                pos=j;
            }
        }
        ans+=mi;
        vis[pos]=1;
        update(pos);    
    }
    return ans;
}

prim O(mlogm) (小根堆优化)

    vector<pll> edge[maxn];
    ll dis[maxn];
    ll vis[maxn];
ll prim(ll n){
    for(ll i=1;i<=n;i++){
        vis[i]=0;
        dis[i]=inf;
    }
    ll ans=0;
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,1});
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        ans+=d;
        for(auto [v,w]:edge[u]){
            if(!vis[v]&&w<dis[v]){
                dis[v]=w;
                pq.push({dis[v],v});
            }
        }
    }
    return ans;
}

kruskal

typedef struct{
    ll u,v,w;
}eg;
    eg e[maxm];
    vector<pll> edge[maxn];
    ll fa[maxn];
bool cmp(eg a,eg b){
    return a.w<b.w;
}
ll find(ll a){
    return (fa[a]==a)?a:(fa[a]=find(fa[a]));
}
void merge(ll a,ll b){
    fa[a]=b;
}
ll kruscal(ll n,ll m){
    for(ll i=1;i<=n;i++){
        fa[i]=i;
    }
    sort(e+1,e+m+1,cmp);
    ll ans=0;
    for(ll i=1;i<=m;i++){
        ll a=find(e[i].u);
        ll b=find(e[i].v);
        if(a!=b){
            merge(a,b);
            ans+=e[i].w;
            n--;
        }
    }
    if(n==1){
        return ans;
    }else{
        return inf;
    }
}
for(ll i=1;i<=m;i++){
    ll u,v,w;
    cin>>u>>v>>w;
    edge[u].push_back({v,w});
    edge[v].push_back({u,w});
    e[i].u=u;e[i].v=v;e[i].w=w;
}

基于倍增的LCA

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define ll long long
#define ull unint long long
#define lowbit(i) ((i) & (-i))
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
#define rep(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, a, b) for (ll i = a; i >= b; i--)

typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll maxn = 5e5 + 200;

    ll n, q, root; 
    vector<ll> mp[N];
    ll lg2[maxn];
    ll dep[maxn];
    ll f[maxn][20];
    ll vis[maxn];
void dfs(ll u, ll fa = 0){
    if (vis[u]) return;
    vis[u] = 1;
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (ll i = 1; i <= lg2[dep[u]]; i++){
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for (auto v : mp[u]){
        dfs(v, u);
    }
}
ll lca(ll a, ll b){
    if (dep[a] > dep[b])
        swap(a, b);
    while (dep[a] != dep[b])
        b = f[b][lg2[dep[b] - dep[a]]];
    if (a == b)
        return a;
    for (ll k = lg2[dep[a]]; k >= 0; k--){
        if (f[a][k] != f[b][k]){
            a = f[a][k], b = f[b][k];
        }
    }
    return f[a][0];
}
int main(){
    IOS 
    cin >> n >> q >> root;
    for (ll i = 1; i < n; i++){
        ll u, v;
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    for (ll i = 2; i <= n; i++){
        lg2[i] = lg2[i / 2] + 1;
    }
    dfs(root);
    while (q--){
        ll u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}

有向图强联通分量

有向非强连通图中的极大强连通子图我们称为强连通分量

如果一个有向图不是强连通图但是将所有有向边换成无向边变成了强连通图，那么该图就是弱连通图。

Kosaraju算法

首先对原图$G$进行遍历，记录节点访问完的顺序$d_i$，$d_i$ 表示第$i$个访问完的节点编号。

我们选择最晚访问完的节点，对$G$的反向图进行遍历，它能够遍历到的顶点和它组成了一个 SCC，把该过程所遍历到的节点打标记，接下来继续找最晚访问完且未被打上标记的节点进行遍历操作。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=1e5+7;
int n,m;
vector<int>e[Maxn],e1[Maxn];
// e 存正向边,e1 存反向边 
bool vis[Maxn];
int d[Maxn],cnt,col[Maxn],cnt1;
void dfs1(int u){
	vis[u]=1;
	for(auto v:e[u]) if(!vis[v]) dfs1(v);
	d[++cnt]=u;
}
vector<int>ans[Maxn];
void dfs2(int u){
	col[u]=cnt1;
	ans[cnt1].push_back(u);
	for(auto v:e1[u]) if(!col[v]) dfs2(v);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e1[v].push_back(u);
	}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
	for(int i=n;i;i--) if(!col[d[i]]) ++cnt1,dfs2(d[i]);
	for(int i=1;i<=cnt1;i++) sort(ans[i].begin(),ans[i].end());
	printf("%d\n",cnt1);
	for(int i=1;i<=n;i++){
		if(ans[col[i]].size()){
			for(auto j:ans[col[i]]) printf("%d ",j);
			puts("");
			ans[col[i]].resize(0);
		}
	}
	return 0;
}

Tarjan算法

在 DFS 过程中，我们会遇到如下 4 种边：

  • 树枝边：DFS 过程中经过的边，即 DFS 搜索树上的边。

  • 前向边：从祖先节点指向后代节点的非树枝边，我们称为前向边。

  • 返祖边（后向边）：从后代节点指向祖先节点的非树枝边，我们称为返祖边（后向边）。

  • 横叉边：两端无祖先关系的非树枝边，我们称为横叉边。

    每个强连通分量都是 DFS 树的一颗子树，搜索时，把当前 DFS 树种未处理的节点加入一个栈，回溯时可以判断栈顶到栈中的节点是否构成一个强连通分量。

我们不妨定义$dfn(u)$表示节点$u$在 DFS 中的遍历编号（时间戳），$low(u)$表示$u$或$u$的子树能够最多只通过**一条非树枝边（不包含树边）**回溯的最早的$dfn$值，用一个栈记录经过的节点，那么我们可以得出：

  • 初始情况有$low(u)=dfn(u)$。
  • 对于边$(u,v)$ ，如果$u$为$v$的父亲节点，则有$low(u)=min(low(u),low(v))$。
  • 对于边$(u,v)$为返祖边或者指向非其他强连通的横叉边，则有$low(u)=min(low(u),dfn(v))$。

在节点$u$搜索完毕之后，如果$low(u)=dfn(u)$，那么说明以$u$为根节点的搜索子树上及栈中在$u$内的元素组成了一个强连通分量，然后删除栈内的这些元素，不断重复该操作直到找到所有的强连通分量。

例 P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=1e5+7;
int n,m;
vector<int>e[Maxn];
int col[Maxn],dfn[Maxn],low[Maxn],cnt;
int stk[Maxn],top,_cnt;
vector<int>ans[Maxn];
void Tarjan(int u){
	dfn[u]=low[u]=++cnt;
	stk[++top]=u;
	for(auto v:e[u]){
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(!col[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		col[u]=++_cnt;
		ans[_cnt].push_back(u);
		while(stk[top]!=u) 	
			ans[_cnt].push_back(stk[top]),col[stk[top--]]=_cnt;
		--top;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=_cnt;i++) sort(ans[i].begin(),ans[i].end());
	printf("%d\n",_cnt);
	for(int i=1;i<=n;i++){
		if(ans[col[i]].size()){
			for(auto j:ans[col[i]]) printf("%d ",j);
			puts("");
			ans[col[i]].resize(0);
		}
	}
	return 0;
}

割点割边

  • 割点：在无向图中，删去该点后使得连通块数增加的结点称为 割点。
  • 割边（桥）：在无向图中，删去该边后使得连通块数增加的边称为 割边（桥）。

一个图可能会有多个割点或者割边，但是有割点的图不一定存在割边，有割边的图不一定存在割点。

割点

和有向图求 SCC 一样，我们会在搜索过程中遇到两种搜索树上的边：

  • 树枝边：DFS 过程中经过的边，即 DFS 搜索树上的边。
  • 返祖边（后向边）：从后代节点指向祖先节点的非树枝边，我们称为返祖边（后向边）。

不包含横叉边和前向边，因为这是无向图。

我们不妨定义$dfn(u)$表示节点$u$在 DFS 中的遍历编号（时间戳），$low(u)$ 表示$u$或$u$的子树能够最多只通过**一条非树枝边（不包含树边）**回溯的最早的$dfn$值，那么我们可以得出：

  • 初始情况有$low(u)=dfn(u)$。
  • 对于边$(u,v)$，如果$v$没有被搜索到，那么这条边就是树枝边，则有$low(u)=min(low(u),low(v))$。
  • 对于边$(u,v)$，如果$v$被搜索到了，那么这条边就是返祖边，则有$low(u)=min(low(u),dfn(v))$。

对于一个节点$u​$，它的子节点$v​$，若$low(v)\geq dfn(u)​$，说明$v​$无法通过它子树的节点到达$dfn​$更小的节点，也就是$v​$无法不经过点$u​$到达比$u​$的$dfn​$值更小的节点，显然$u​$是一个割点，反之 𝑢 $u​$就不是一个割点。

但是对于根节点$u$，它的$dfn$值一定是整个序列的最小值，因此上述方法不管用，如果它存在两个及以上的子节点，那么把$u$删除后绝对会把$u$子节点的子树分割开来，此时$u$是割点。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=1e5+7;
struct edge1{
	ll v,Next;
}Edge[Maxn<<1];
ll n,m,tot,low[Maxn],dfn[Maxn],cnt,root,ans,head[Maxn];
bool flg[Maxn];
inline void add(ll u,ll v){
	Edge[++tot]=(edge1){v,head[u]},head[u]=tot;
}
void tarjan(ll u){
	dfn[u]=low[u]=++cnt;
	ll ch=0;
	for(ll i=head[u];i;i=Edge[i].Next){
		ll v=Edge[i].v;
		if(!dfn[v]){
			ch++;
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=root) flg[u]=1;
			
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(ch>=2&&root==u) flg[u]=1;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1,u,v;i<=m;i++) 
		scanf("%lld%lld",&u,&v),add(u,v),add(v,u); 
	for(ll i=1;i<=n;i++)
		if(!dfn[i])
			root=i,tarjan(i);
	for(ll i=1;i<=n;i++)
		if(flg[i])
			++ans;
	printf("%lld\n",ans);
	for(ll i=1;i<=n;i++)
		if(flg[i])
			printf("%lld ",i);
	return 0;
}

割边

割边的求法和割点的求法类似，我们继续使用相同定义的$low$和$dfn$。

很显然，树枝边使得整个图连通，而非树边删除后并不影响图的连通性，因此割边一定是树枝边。

假设当前节点为$u$，它有子节点$v$，那么边$(u,v)$为割边时当且仅当$low(v) > dfn(u)$，只要$v$的节点能通过非树边来到比$u$的$dfn$更小的节点，那么$u,v$就不是割边，不取等号的原因是它是一条边而非一个节点。

现在唯一的问题就是判断一条边是否为非树边，我们不能直接将$v \rightarrow u​$（$u​$是$v​$的父亲）识别成非树边，这样可能将树边也识别成非树边。

tarjan

#include<bits/stdc++.h>
#define int long long
const int N=1e6+1;
using namespace std;
struct fy
{
	int v,next;
}edge[N];
struct fy_
{
	int from,to;
}E[N];
int dfn[N],low[N],n,m,x,y,idx,head[N],res,cnt,IDX;
bool g[N];
inline void add(int x,int y)
{
	edge[++cnt].v=y,edge[cnt].next=head[x],head[x]=cnt;
}
inline void dfs(int u,int fa)
{
	dfn[u]=low[u]=++idx;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].v;
		if(!dfn[v])
		{
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				E[++IDX].from=min(u,v),E[IDX].to=max(u,v);
		}
		else if(v!=fa&&dfn[v]<dfn[u])
			low[u]=min(low[u],dfn[v]);
	}
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,-1);
	for(int i=1;i<=IDX;i++)
		printf("%lld %lld\n",E[i].from,E[i].to);
}

树上差分

对于每一条非树边，在其树上深度较小的点处打上 -1 标记，在其树上深度较大的点处打上 +1 标记。然后求出每个点的子树内部的标记之和。对于一个点u，其子树内部的标记之和等于覆盖了 u和u的父亲之间的树边的非树边数量。若这个值非0，则u和u的父亲之间的树边不是桥，否则是桥。

双联通分量

双连通分量分为点双连通分量和边双连通分量。

边双连通具有传递性，点双连通 不 具有传递性

  • 点双连通图：不存在割点的无向连通图我们称为点双联通图。

  • 边双连通图：不存在割边的无向连通图我们称为边双联通图。

  • 点双连通分量（点双）：一张图的极大点双连通子图称为点双连通分量（V-BCC）。

  • 边双连通分量（边双）：一张图的极大边双连通子图称为边双连通分量（E-BCC）。

  • 点双连通：若两点$u,v$在同一个点双连通分量内，那么我们称$u,v$点双连通。

  • 边双联通：若两点$u,v$在同一个边双连通分量内，那么我们称$u,v$边双连通。

    在一张无向图中，如果$(u,v)$直接相连，那么$u,v$点双连通，但不一定边双连通。

    同时，双连通分量还有一个很好的性质，我们将强连通分量缩点后可以得到一个 DAG，但是双连通分量缩点之后可以得到一棵树，也就是我们在进阶中要讲的圆方树。

边双连通分量

边双连通分量事实上很好求。

我们只需将该无向图的所有割边删去，整张图就会分裂成割边数量+1个联通块，这些联通块内不存在割边，也就是该图分裂成了若干个边双连通分量。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=4e6+7;
struct edge1{
	ll u,v,Next;
}Edge[Maxn<<1];
ll n,m,tot=1,f[Maxn];
ll low[Maxn],dfn[Maxn],cnt,head[Maxn];
ll cl;
vector<ll>ans[Maxn];
bool flg[Maxn],vis[Maxn];
inline void add(ll u,ll v){
	Edge[++tot]=(edge1){u,v,head[u]},head[u]=tot;
}
void tarjan(ll u){
	dfn[u]=low[u]=++cnt;
	for(ll i=head[u];i;i=Edge[i].Next){
		if(i==(f[u]^1)) continue;
		ll v=Edge[i].v;
		if(!dfn[v]){
			f[v]=i;
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]) flg[i]=flg[i^1]=1;
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
void DFS(ll u){
	vis[u]=1;
	ans[cl].push_back(u);
	for(ll i=head[u];i;i=Edge[i].Next){
		if(!flg[i]&&!vis[Edge[i].v]){
			DFS(Edge[i].v);
		}
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1,u,v;i<=m;i++) 
		scanf("%lld%lld",&u,&v),add(u,v),add(v,u); 
	for(ll i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	for(ll i=1;i<=n;i++) if(!vis[i]) ++cl,DFS(i);
	printf("%lld\n",cl);
	for(ll i=1;i<=cl;i++,puts("")){
		printf("%lld ",ans[i].size());
		for(auto j:ans[i]) printf("%lld ",j);
	}
	return 0;
}

点双连通分量

对于一个点双，它在 DFS 搜索树中$dfn$值最小的点一定是割点或者树根。

当这个点是割点时，它所属的点双必定不可以向它的父亲方向包括更多点，因为一旦回溯，它就成为了新的子图的一个割点，不是点双。所以它应该归到其中一个或多个子树里的点双中。

当这个点是树根时，它的$dfn$值是整棵树里最小的。它若有两个以上子树，那么它是一个割点；它若只有一个子树，它一定属于它的直系儿子的点双，因为包括它；它若是一个独立点，视作一个单独的点双。

换句话说，一个点双一定在这两类点的子树中。

我们用栈维护点，当遇到这两类点时，将子树内目前不属于其它点双的非割点或在子树中的割点归到一个新的点双。注意这个点可能还是与其它点双的公共点，所以不能将其出栈。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, M = 4e6 + 5;
int cnt = 1, fir[N], nxt[M], to[M];
int s[M], top, bcc, low[N], dfn[N], idx, n, m;
vector<int> ans[N];
inline void tarjan(int u, int fa) {
	int son = 0;
	low[u] = dfn[u] = ++idx;
	s[++top] = u;
	for(int i = fir[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			son++;
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
				bcc++;
				while(s[top + 1] != v) ans[bcc].push_back(s[top--]);//将子树出栈
				ans[bcc].push_back(u);//把割点/树根也丢到点双里
			}
		} else if(v != fa) low[u] = min(low[u], dfn[v]);
	}
	if(fa == 0 && son == 0) ans[++bcc].push_back(u);//特判独立点
}
inline void add(int u, int v) {
	to[++cnt] = v;
	nxt[cnt] = fir[u];
	fir[u] = cnt;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	for(int i = 1; i <= n; i++) {
		if(dfn[i]) continue;
		top = 0;
		tarjan(i, 0);
	}
	printf("%d\n", bcc);
	for(int i = 1; i <= bcc; i++) {
		printf("%d ", ans[i].size());
		for(int j : ans[i]) printf("%d ", j);
		printf("\n");
	}
	return 0;
}

树链剖分 HLD

using ll = long long;
using Graph = vector<vector<int>>;
struct HLD
{
    vector<int> id, sz, son, fa, top, dep;
    int root, tot;
    Graph g;

    HLD() {};

    HLD(int _n, int _root = 1)
    {
        init(_n + 1, _root);
    }

    HLD(Graph &_g, int _root = 1)
    {
        init(_g, _root);
    }

    // fundamental functions
    void init(Graph &_g, int _root)
    {
        g = _g;
        id.resize(_g.size());
        sz.resize(_g.size());
        son.resize(_g.size());
        fa.resize(_g.size());
        top.resize(_g.size());
        dep.resize(_g.size());
        tot = 0;
        root = _root;

        calc();
    }

    void init(int n, int _root)
    {
        id.resize(n);
        sz.resize(n);
        son.resize(n);
        fa.resize(n);
        top.resize(n);
        dep.resize(n);
        tot = 0;
        root = _root;
        g.assign(n, {});
        // remember calc()
    }

    void calc()
    { // prepare fa, sz, dep, son(heavy son)
        function<void(int, int)> dfs = [&](int now, int f)
        {
            fa[now] = f;
            sz[now] = 1;
            dep[now] = dep[f] + 1;
            for (auto i : g[now])
                if (i != f)
                {
                    dfs(i, now);
                    sz[now] += sz[i];
                    if (sz[i] > sz[son[now]])
                        son[now] = i;
                }
        };
        dfs(root, root);

        // id -> dfn; top -> head of the chain
        dfs = [&](int now, int f)
        {
            top[now] = f;
            id[now] = ++tot;
            if (son[now] == 0)
                return;
            dfs(son[now], f); // heavy chain
            for (auto i : g[now])
                if (i != fa[now] && i != son[now])
                    dfs(i, i); // light chain
        };
        dfs(root, root);
    }

    void addEdge(int u, int v)
    {
        g[u].push_back(v), g[v].push_back(u);
    }

    // tool functions
    int lca(int x, int y)
    {
        while (top[x] != top[y])
        {
            if (dep[top[x]] > dep[top[y]])
                x = fa[top[x]];
            else
                y = fa[top[y]];
        }
        return (dep[x] > dep[y]) ? y : x;
    }

    int dist(int u, int v)
    {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
};

处理：

  • 以 u 为根的子树在 id[u], id[u] + sz[u] - 1 区间上。
  • 处理两点间简单路径的实例，其中update是区间加。
void pathAdd(int u, int v, int x)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        update(id[top[u]], id[u], x);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v])
        swap(u, v);
    update(id[u], id[v], x);
}
  • 对u, v之间简单路径做树上差分的做法是 tag[u]++, tag[v]++, tag[lca]--, tag[fa[lca]]--。

二分图最大匹配问题

匈牙利算法

用于解决二分图最大匹配问题（如：存在若干男女及其喜欢关系（没有同性恋），求最大匹配数/匹配时人不可重复使用）

dfs解：P3386 二分图最大匹配 洛谷

	//男女生模型
    vector<ll> edge[maxn];//edge[u]里面有v代表男生u和女生v可以相连
    ll vis[maxn];//vis[v],在该次dfs下，女生v是否已经配对
    ll match[maxn];//match[v]=u,女生v和男生u配对
bool dfs(ll now){
    for(auto t:edge[now]){
        if(vis[t]) continue;
        vis[t]=1;
        if(!match[t]||dfs(match[t])){
            match[t]=now;
            return true;
        }
    }
    return false;
}
void solve(){
    ll n,m,e;
    cin>>n>>m>>e;
    rep(i,1,e){
        ll u,v;
        cin>>u>>v;
        edge[u].push_back(v);
    }
    ll ans=0;
    rep(i,1,n){
        rep(j,1,m){
            vis[j]=0;
        }
        if(dfs(i)) ans++;
    }
    cout<<ans<<endl;
}

这道题比较特殊，两类点是可以在一开始就明确分好的，下面给出一个未知分类的，较为通用的解

    vector<ll> edge[maxn];
    ll vis[maxn];
    ll match[maxn];
    ll tag;
bool dfs(ll now){
    for(auto t:edge[now]){
        if(vis[t]==tag) continue;
        vis[t]=tag;
        if(!match[t]||dfs(match[t])){
            match[t]=now;
            match[now]=t;
            return true;
        }
    }
    return false;
}
ll hungarian(ll n,ll m){
    ll ans=0;
    rep(i,1,n){
        if(match[i]) continue;
        tag=i;//类似时间戳
        if(dfs(i)) ans++;
    }
    return ans;
}

差分约束

给出一组包含m个不等式，n个未知数的不等式组

​形如：$x_i$-$x_j$<=$y_k$

求满足这个不等式组的非负解，并且每个变量尽量小

n,m<=5e3, -1e4<=y<=1e4

输出n个数，若无解则输出-1

无解判断

对每一个scc，如果其中全部边边权都为0，则有解，否则无解

有解后可以通过缩点化为dag

求一组解：

o(n*m)

类似bellman-ford

cin>>n>>m;
vector<array<int,3>>e;
for(int i=1;i<=m;i++){
	int l,r,w;cin>>l>>r>>w;
	e.push_back({l,r,w});
}
for(int i=0;i<=n;i++){
	for(auto [l,r,w]:e){
		x[l] = min(x[l],x[r]+w);
	}
}
for(auto [l,r,w]:e){
	if(x[l]>x[r]+w){
		cout<<-1<<endl;return;
	}
}
for(int i=1;i<=n;i++){
	cout<<x[i]<<" ";
}cout<<endl;

为了求非负解，令x[0]=0;

添加条件 $x_0$ - $x_i$ <= 0

for(int i=1;i<=n;i++){
	e.push_back(0,i,0);
}
for(int i=1;i<=n;i++){
	x[i] = 1<<30;
}

通过这样求出来的是满足条件的最大值

为了求最小值，可以转化不等式为 $x_j$ >= $x_i$ - $w$;

存储部分不变

迭代代码变为：

for (int i=0;i<=n;i++){
	for(auto [l,r,w]:e){
		x[r] = max(x[r],x[l]-w);
	}
}

迭代部分也可利用spfa或dijstra优化

例：

题目描述

给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

$$ \begin{cases} x_{c_1}-x_{c'1}\leq y_1 \x{c_2}-x_{c'2} \leq y_2 \ \cdots\ x{c_m} - x_{c'_m}\leq y_m\end{cases}$$

的不等式组，求任意一组满足这个不等式组的解。

输入格式

第一行为两个正整数 $n,m$，代表未知数的数量和不等式的数量。

接下来 $m$ 行，每行包含三个整数 $c,c',y$，代表一个不等式 $x_c-x_{c'}\leq y$。

输出格式

一行，$n$ 个数，表示 $x_1 , x_2 \cdots x_n$ 的一组可行解，如果有多组解，请输出任意一组，无解请输出 NO。

样例 #1

样例输入 #1
3 3
1 2 3
2 3 -2
1 3 1
样例输出 #1
5 3 5

数据范围

对于 $100%$ 的数据，$1\leq n,m \leq 5\times 10^3$，$-10^4\leq y\leq 10^4$，$1\leq c,c'\leq n$，$c \neq c'$。

题解

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,a,b) for(ll i=a;i<=b;++i)
using namespace std;
#define int long long
// const ll maxn=10+1e5;
const long long mod = 998244353;

const int N = 5010;
const int M = 5010;
int n,m;
vector<array<int,3>>e;
int x[5010];
void solve()
{   
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e.push_back({u,v,w});
    }
    for(int i=1;i<=n;i++){
        for(auto [u,v,w]:e){
            x[u] = min(x[u],x[v]+w);
        }
    }
    for(auto [u,v,w]:e){
        if(x[u]>x[v]+w){
            cout<<"NO"<<endl;return;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<x[i]<<" ";
    }cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll T=1; 
    //cin>>T;
    while(T--){
        solve();
    }
}

2-sat

2-SAT，简单的说就是给出n个集合，每个集合有两个元素，已知若干个<a,b>，表示 a与b矛盾（其中a与 b属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 n个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。

eg.P4782 【模板】2-SAT - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

【模板】2-SAT

题目描述

有 $n$ 个布尔变量 $x_1$$\sim$$x_n$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$x_i$ 为 true / false 或 $x_j$ 为 true / false」。比如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

输入格式

第一行两个整数 $n$ 和 $m$，意义如题面所述。

接下来 $m$ 行每行 $4$ 个整数 $i$, $a$, $j$, $b$，表示 「$x_i$ 为 $a$ 或 $x_j$ 为 $b$」($a, b\in {0,1}$)

输出格式

如无解，输出 IMPOSSIBLE；否则输出 POSSIBLE。

下一行 $n$ 个整数 $x_1\sim x_n$（$x_i\in{0,1}$），表示构造出的解。

样例 #1

样例输入 #1
3 1
1 1 3 0
样例输出 #1
POSSIBLE
0 0 0

提示

$1\leq n, m\leq 10^6$ , 前 $3$ 个点卡小错误，后面 $5$ 个点卡效率。

由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。

思路

对[i,a,j,b]

化成两条边 $\lnot i \to j$ 、 $\lnot j \to j$

对建好的图跑tarjan

若最终存在 i 使得 $\lnot i$和i在同一个scc中，则无解，否则取拓扑序中靠后的元素

题解

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,a,b) for(ll i=a;i<=b;++i)
using namespace std;
#define int long long
// const ll maxn=10+1e5;
const long long mod = 998244353;

const int N = 2000005;
const int M = 2000005;
vector<int>e[N];
int col[N],dfn[N],low[N],cnt;
int stk[N],top,_cnt;
vector<int>ans[N];

int n,m;
void Tarjan(int u){
	dfn[u]=low[u]=++cnt;
	stk[++top]=u;
	for(auto v:e[u]){
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(!col[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		col[u]=++_cnt;
		ans[_cnt].push_back(u);
		while(stk[top]!=u) 	
			ans[_cnt].push_back(stk[top]),col[stk[top--]]=_cnt;
		--top;
	}
}

void solve()
{   cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,a,v,b;cin>>u>>a>>v>>b;
        u--;v--;
        u=2*u+a;
        v=2*v+b;
        e[u^1].push_back(v);
        e[v^1].push_back(u);
    }
    for(int i=0;i<2*n;i++){
        if(!dfn[i]){
            Tarjan(i);
        }
    }
    for(int i=0;i<2*n;i+=2){
        if(col[i]==col[i^1]){
            cout<<"IMPOSSIBLE"<<endl;return;
        }
    }
    cout<<"POSSIBLE"<<endl;
    for(int i=0;i<2*n;i+=2){
        if(col[i]<col[i^1]){//此时非i拓扑序更靠后
            cout<<0<<" ";
        }
        else{
            cout<<1<<" ";
        }
    }
    cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll T=1; 
    //cin>>T;
    while(T--){
        solve();
    }
}

[JSOI2010] 满汉全席

题目描述

满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在数量繁多的菜色之中。由于菜色众多而繁杂，只有极少数博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。

为了招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在参赛的厨师之中，找到满汉界的明日之星。

大会的规则如下：每位参赛的选手可以得到 $n$ 种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。

大会的评审制度是：共有 $m$ 位评审员分别把关。每一位评审员对于满汉全席有各自独特的见解，但基本见解是，要有两样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就不能算是满汉全席。但避免过于有主见的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出来的状况下，才能淘汰一位选手，否则不能淘汰一位选手。

换句话说，只要参赛者能在这两种材料的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表：

评审一 评审二 评审三 评审四 
满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 
汉式猪肉 满式羊肉 汉式猪肉 满式羊肉

如参赛者甲做出满式猪肉，满式羊肉和满式牛肉料理，他将无法满足评审三的要求，无法通过评审。而参赛者乙做出汉式猪肉，满式羊肉和满式牛肉料理，就可以满足所有评审的要求。

但大会后来发现，在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话，所有的参赛者最多只能通过部分评审员的审查而不是全部，所以可能会发生没有人通过考核的情形。

如有四个评审员喜好如下表时，则不论参赛者采取什么样的做法，都不可能通过所有评审的考核：

评审一 评审二 评审三 评审四 
满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 
汉式猪肉 满式羊肉 汉式猪肉 满式猪肉

所以大会希望有人能写一个程序来判断，所选出的 $m$ 位评审，会不会发生没有人能通过考核的窘境，以便协会组织合适的评审团。

输入格式

第一行包含一个数字 $K$（$1\le K \le 50$），代表测试文件包含了 $K$ 组数据。

每一组测试数据的第一行包含两个数字 $n$ 跟 $m$（$n≤100$，$m≤1000$），代表有 $n$ 种材料，$m$ 位评审员。

为方便起见，舍弃做法的中文名称而给予编号，编号分别从 $1$ 到 $n$。

接下来的 $m$ 行，每行都代表对应的评审员所拥有的两个喜好，每个喜好由一个英文字母跟一个数字代表，如 $m1$ 代表这个评审喜欢第 $1$ 个材料透过满式料理做出来的菜，而 $h2$ 代表这个评审员喜欢第 $2$ 个材料透过汉式料理做出来的菜。

输出格式

每组测试数据输出一行，如果不会发生没有人能通过考核的窘境，输出 GOOD；否则输出 BAD（均为大写字母）。

样例 #1

样例输入 #1
2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2
样例输出 #1
GOOD
BAD

题解

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,a,b) for(ll i=a;i<=b;++i)
using namespace std;
#define int long long
// const ll maxn=10+1e5;
const long long mod = 998244353;

const int N = 2010;
const int M = 2010;
vector<int>e[N];
int col[N],dfn[N],low[N],cnt;
int stk[N],top,_cnt;
vector<int>ans[N];

int n,m;
void Tarjan(int u){
	dfn[u]=low[u]=++cnt;
	stk[++top]=u;
	for(auto v:e[u]){
		if(!dfn[v]) Tarjan(v),low[u]=min(low[u],low[v]);
		else if(!col[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		col[u]=++_cnt;
		ans[_cnt].push_back(u);
		while(stk[top]!=u) 	
			ans[_cnt].push_back(stk[top]),col[stk[top--]]=_cnt;
		--top;
	}
}

void solve()
{   cin>>n>>m;
    cnt=0;_cnt=0;top=0;
    for(int i=0;i<2*n;i++){
        e[i].clear();
        dfn[i]=0;
        low[i]=0;
        col[i]=0;
        ans[i].clear();
    }
    for(int i=1;i<=m;i++){
        char x,y;int u,v;
        cin>>x;
        cin>>u;
        cin>>y;
        cin>>v;
        u--;v--;//0 - n-1
        //cout<<u<<"  "<<v<<endl;
        u = 2*u+(x=='m');
        v = 2*v+(y=='m');

        e[u^1].push_back(v);
        e[v^1].push_back(u);
    }

    for(int i=0;i<2*n;i++){
        if(!dfn[i]){
            Tarjan(i);
        }
    }
    for(int i=0;i<2*n;i+=2){
        if(col[i]==col[i^1]){
            cout<<"BAD"<<endl;
            return;
        }
    }
    cout<<"GOOD"<<endl;
    return;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll T=1; 
    cin>>T;
    while(T--){
        solve();
    }
}