定理整理：
关于二分图：
(1) 二分图的最小路径覆盖
1.最小不相交路径覆盖 ：Res==节点数-最大匹配数
2.最小可相交路径覆盖：首先floyd算法跑出所有可以到达的点，之后Res==节点数-最大匹配数
(2)二分图的最小顶点覆盖：
定义：若选择一个点说明选择与它相连的所有边，最小顶点覆盖就是选择最少的点来覆盖所有的边。
最小定点覆盖==二分图最大匹配
(3)二分图最大独立集
定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。最大独立集为包含顶点数最多的独立集。
定理：最大独立集 = 所有顶点数 - 最小顶点覆盖 =最小路径覆盖
(4)二分图的最大团
定义： 团：选出一些点，使其两两之间都有边。 最大团：点数最大的团
定理：二分图的最大团 = 补图的最大独立集
感性理解：最大独立集为两两之间没有边，那么补图的最大独立集说明在原图中两两之间有边，那么就是原图的最大团
(5)极大匹配(Maximal Matching)：是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
(6)最大匹配(maximum matching)：是所有极大匹配当中边数最大的一个匹配,设为M。选择这样的边数最大的子集称为图的最大匹配问题。
(7)完美匹配（完备匹配）：一个图中所有的顶点都是匹配点的匹配，即2|M| = |V|。完美匹配一定是最大匹配，但并非每个图都存在完美匹配。
(8)最优匹配：最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同，最优匹配也是一个完备匹配，即每个顶点都被匹配。如果个数不相等，可以通过补点加0边实现转化。一般使用KM算法解决该问题。（KM（Kuhn and Munkres）算法，是对匈牙利算法的一种贪心扩展。）
关于欧拉图:
(1)无向图存在欧拉回路的充要条件
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
因为要遍历完所有的边,所以每一个点而言,只要有进去的边,就一定要有出去的边
(2)有向图存在欧拉回路的充要条件
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
同无向图
关于其他一般图
(1)拓扑排序:
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
Others Continue...
模板整理：
1.二分图匈牙利匹配：
bool used[maxn];
int girl[maxn];
int boy[maxn];
bool judge(int x)
{
int sz=v[x].size();
for(int k=0;k<sz;k++)
{
ll e=v[x][k];
if(!used[e])
{
used[e]=true;
if(!girl[e]||judge(girl[e]))
{
girl[e]=x;
boy[x]=e;
return true;
}
}
}
return false;
}
//MaxMatch()
for(int i=1;i<=n;i++)
{
for(int k=1;k<=m;k++) used[k]=false;
if(judge(i)&&boy[i]==-1) p++;//boy数组自己开
} 2.二分图染色
bool dfs(int u,int c)
{
vis[u]=c;
int sz=v[u].size();
for(int i=0;i<sz;i++)
{
int e=v[u][i];
if(vis[e]==c) return false;
if(!vis[e]&&!dfs(e,-c)) return false;
}
return true;
}
//判断是否为二分图
for(int i=1;i<=n;i++)
if(vis[i]==0&&!judge(i)) //不是二分图
//否则则是并已成功染色 3.Hopcroft-Karp匹配算法 O（sqrt（n）*m） 【带优化】
/***
主函数加 memeset()
***/
ll n,m,p;
int dR[maxn],dL[maxn];//增广路距离
int nR[maxn],nL[maxn];//左右标记
bool used[maxn];//使用标记
ll cnt=0,dis;
vector<int>v[maxn];//邻接表
bool judge()//寻找最短增广路
{
queue<int>q;
memset(dR,-1,sizeof(dR));
memset(dL,-1,sizeof(dL));
for(int i=1;i<=cnt;i++)//cnt 换成 y集有多少个点
{
if(nL[i]==-1){
q.push(i);
dL[i]=0;
}
}
dis=INF;
while(!q.empty())
{
int u=q.front();q.pop();
if(dL[u]>dis) break;
int sz=v[u].size();
for(int i=0;i<sz;i++)
{
int e=v[u][i];
if(dR[e]==-1)//保证增广路不相交
{
dR[e]=dL[u]+1;
if(nR[e]==-1) dis=dR[e];
else{
dL[nR[e]]=dR[e]+1;
q.push(nR[e]);
}
}
}
}
return dis!=INF;
}
bool Find(int x)
{
int sz=v[x].size();
for(int i=0;i<sz;i++)
{
int e=v[x][i];
if(dR[e]==dL[x]+1&&!used[e])
{
used[e]=true;
if(nR[e]!=-1&&dis==dR[e]) continue;//优化
if(nR[e]==-1||Find(nR[e]))
{
nR[e]=x;
nL[x]=e;
return true;
}
}
}
return false;
}
ll MaxMatch()
{
ll res=0;
while(judge())
{
memset(used,false,sizeof(used));
for(int i=1;i<=n;i++)
if(nL[i]==-1&&Find(i)) res++;
}
return res;
} 4.KM算法,带权图最佳匹配
/***
不是完全图的边补成完全图 补0
slack的本质优化:
slack表示的是 右边到左边最小的差值,也就是说 上一次匹配过程中 如果要形成增广路最少减少多少
***/
const int INF = 0x3f3f3f3f;
int mp[1005][1005];// 完全图 无边补0
int nL[1005],nR[1005];//左边与右边匹配的点
int xL[1005],xR[1005];//可行性顶标
bool L[1005], R[1005];//标记是否在一轮匹配中被匹配过
int slack[1005];//优化松弛数组
ll n,m;
bool hungry(int x)
{
L[x]=true;
for(int i=1;i<=n;i++)
{
int gap=xL[x]+xR[i]-mp[x][i];
if(gap==0)
{
if(!R[i])
{
R[i]=true;
if(nR[i]==-1||hungry(nR[i]))
{
nR[i]=x;
nL[x]=i;
return true;
}
}
}
else
slack[i]=min(slack[i],gap);
}
return false;
}
ll km()
{
memset(xR,0,sizeof(xR));
memset(xL,0,sizeof(xL));
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
xL[i]=max(xL[i],mp[i][k]);
for(int i=1;i<=n;i++)
{
for(int k=1;k<=n;k++) slack[k]=INF;
while(1)
{
memset(L,false,sizeof(L));
memset(R,false,sizeof(R));
if(hungry(i)) break;
int d=INF;
for(int k=1;k<=n;k++)
if(!R[k]) d=min(slack[k],d);
for(int k=1;k<=n;k++)
{
if(L[k]) xL[k]-=d;
if(R[k]) xR[k]+=d;
else slack[k]-=d;//因为没有被访问过,但是左边的预期值
}
}
}
ll res=0;
for(int i=1;i<=n;i++)
res+=mp[nR[i]][i];
return res;
} 5.km算法求最小权值匹配 (带权图 最小费用圈覆盖 )
/****
与上面模板相同 mp数组初始化为-INF
其余不变
最后结果取反即可
****/ 6.匈牙利算法 多重匹配：n^3~n^4 可解决最小化分组问题
vector<int>v[1500];
bool used[1500];
vector<int>nR[1500];
bool dfs(int x)
{
int sz=v[x].size();
for(int i=0;i<sz;i++)
{
int e=v[x][i];
if(!used[e])
{
used[e]=true;
int sz=nR[e].size();
if(sz<limit)
{
nR[e].push_back(x);
return true;
}
else
{
for(int k=0;k<sz;k++)
{
if(dfs(nR[e][k]))
{
nR[e][k]=x;
return true;
}
}
}
}
}
return false;
} 6.djistra+堆优化的最短路(N+vlgv)
struct N{
int id;
ll w;
bool friend operator<(N a,N b)
{
return a.w>b.w;
}
};
void dijstra()
{
for(int i=1;i<=n;i++) dis[i]=INF;
dis[1]=0;
N s;s.id=1;s.w=0;
priority_queue<N>q;
q.push(s);
while(1)
{
if(q.empty()) break;
N u=q.top();q.pop();
if(dis[u.id]!=u.w) continue;
for(int i=head[u.id];~i;i=edge[i].next)
{
int e=edge[i].e;
if(dis[e]>u.w+edge[i].w)
{
dis[e]=u.w+edge[i].w;
N now;now.id=e;
now.w=dis[e];
q.push(now);
}
}
}
return;
} 6.最短路径还原
void AC(int u)
{
if(path[u]!=-1) AC(path[u]);
printf("%d ",u);
} 7.A*第k短路 注释为:严格第k短路
ll n,m,p;//n个点,m条边,第p短路
int s,t;//起点和终点
ll cnt=0,cnt1=0;
int head[maxn],head1[maxn];//正向建图,反向建图
ll dis[5005];
bool vis[5005];
int shirt[5005];
struct edg{
int e,next;
ll w;
}edge[maxn],edge1[maxn];
struct node
{
int id;ll g;
friend bool operator<(node a,node b)
{
return a.g+dis[a.id]>b.g+dis[b.id];
}
};
void restart()
{
memset(head,-1,sizeof(head));
memset(head1,-1,sizeof(head1));
cnt=cnt1=0;
}
void addedge(int u,int v,double w)
{
edge[cnt]=edg{v,head[u],w};
head[u]=cnt++;
edge1[cnt1]=edg{u,head1[v],w};
head1[v]=cnt1++;
}
void spfa()//反向跑最短路
{
for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=false;
queue<int>q;
q.push(t);dis[t]=0;vis[t]=true;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=false;
for(int i=head1[u];~i;i=edge1[i].next)
{
int e=edge1[i].e;
if(dis[e]>dis[u]+edge1[i].w)
{
dis[e]=dis[u]+edge1[i].w;
if(!vis[e])
{
vis[e]=true;
q.push(e);
}
}
}
}
}
ll A_start()
{
ll cot=0;
if(s==t) p++;//如果s==t 因为起点为s 防止cot++;
//ll pre=-1;//严格第k短路
priority_queue<node>q;
q.push(node{s,0});
if(dis[s]==INF) return -1;
while(!q.empty())
{
node u=q.top();q.pop();
if(u.id==t)
{
// if(u.g!=pre) {cot++;pre=u.g;}//严格第k短路
cot++;
}
if(cot==p) return u.g;
shirt[u.id]++;
if(shirt[u.id]>p) continue;
for(int i=head[u.id];~i;i=edge[i].next)
q.push(node{edge[i].e,u.g+edge[i].w});
}
return -1;
} 8.严格/非严格第二短路
void spfa()
{
for(int i=1;i<=n;i++) dis[i]=dis1[i]=INF,vis[i]=false;
queue<N>q;dis[1]=0;
vis[1]=true;N s;s.w=0;s.id=1;q.push(s);
while(!q.empty())
{
N u=q.front();q.pop();
for(int i=head[u.id];~i;i=edge[i].next)
{
int e=edge[i].e;
if(dis[e]>u.w+edge[i].w)
{
dis1[e]=dis[e];
dis[e]=u.w+edge[i].w;
q.push(N{e,dis[e]});
}
else if(dis1[e]>u.w+edge[i].w&&u.w+edge[i].w>dis[e])//非严格去除条件即可
{
dis1[e]=u.w+edge[i].w;
q.push(N{e,dis1[e]});
}
}
}
} 9.spfa判负环
int judge()
{
for(int i=0;i<=n;i++) dis[i]=INF,vis[i]=false;
for(int i=0;i<=n;i++) cot[i]=0;
queue<int>q;q.push(1);vis[1]=true;
dis[1]=0;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=false;
if(cot[u]>n+1) return 1;
for(int i=head[u];~i;i=edge[i].next)
{
int e=edge[i].e;
if(dis[e]>dis[u]+edge[i].w)
{
dis[e]=dis[u]+edge[i].w;
cot[e]++;
if(!vis[e])
{
q.push(e);
vis[e]=true;
}
}
}
}
return 0;
} 10.判断补图的连通性(点的个数 1e6可) 静态链表优化
int head[maxn];
struct node{
int e,next;
}edge[maxn];
int pre[maxn],cur[maxn];
int vis[maxn];//标记每个点是否被访问
int d[maxn];//标记BFS中每个点是否被访问
int res[maxn];//每个联通块有多少个点
ll cnt=0;
void addedge(int u,int v)
{
edge[cnt]=node{v,head[u]};
head[u]=cnt++;
edge[cnt]=node{u,head[v]};
head[v]=cnt++;
}
int main()
{
int cot=0;
memset(head,-1,sizeof(head));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
addedge(x,y);
}
int s=1;
for(int i=1;i<=n;i++){
pre[i]=i-1;
cur[i]=i+1;
}
cur[n]=-1;pre[1]=-1;
pre[1]=-1;cur[n]=-1;
for(int i=1;i<=n;i++)if(!vis[i]){
queue<int>q;q.push(i);
vis[i]=++cot;
res[cot]++;
while(!q.empty())
{
int u=q.front();q.pop();
for(int k=head[u];~k;k=edge[k].next)
{
int e=edge[k].e;
if(!d[e]) d[e]=1;
}
for(int k=s;~k;k=cur[k])
{
if(!d[k])
{
if(!vis[k])
{
cur[pre[k]]=cur[k];
pre[cur[k]]=pre[k];
if(k==s) s++;
vis[k]=cot;
res[cot]++;
q.push(k);
}
}
else
d[k]=0;
}
}
} 11.拓扑排序 复杂度O (n+m)
ll cot=0;
void Topological_Order()
{
queue<int>q;
for(int i=1;i<=n;i++)
if(!in[i]) q.push(i);
cot=0;
while(!q.empty())
{
int u=q.front();q.pop();
res[++cot]=u;
for(int i=head[u];~i;i=edge[i].next)
{
int e=edge[i].e;
in[e]--;
if(in[e]==0) q.push(e);
}
}
if(cot==n){
for(int i=1;i<=cot;i++) printf("%d ",res[i]);
printf("\n");
}
else puts("NO\n");
} 12.有向图判断连通性 (并查集)
int Find(int x)
{
return pre[x]==x?x:pre[x]=Find(pre[x]);
}
void Merge(int x,int y)
{
int dx=Find(x);
int dy=Find(y);
if(dx!=dy)
pre[dx]=dy;
return;
}
int x=Find(1);
for(int i=1;i<=n;i++)
if(Find(i)!=x) //不连通 13.强连通分量 缩点 Tarjan O(n+m)
int dfn[maxn],low[maxn];//dfs序号 他能连接到的最小根节点
int st[maxn],s=0;//栈
int sct[maxn],szsc[maxn],scc=0;//强连通分量所属,强连通分量个数
int inst[maxn];//标记是否在栈中
int cot=0;//dfs序
void Tarjan(int u)
{
st[++s]=u;inst[u]=1;
low[u]=dfn[u]=++cot;
for(int i=head[u];~i;i=edge[i].next)
{
int e=edge[i].e;
if(!dfn[e]){
Tarjan(e);
low[u]=min(low[u],low[e]);
}
else if(inst[e]) low[u]=min(low[u],dfn[e]);
//else 被访问过并且不在栈里 那肯定已经为强连通分量了
}
if(low[u]==dfn[u]){
scc++;//强连通分量++
while(1)
{
int x=st[s--];
inst[x]=0;
sct[x]=scc;
szsc[scc]++;//强连通分量的大小为1
if(u==x) break;
}
}
} 13.最大度生成树 优先队列每次选择度最大的
struct Degree{
int w;
int id;
bool friend operator<(Degree a,Degree b)
{
return a.w>b.w;
}
};
void bfs()
{
Degree s;s.w=-1;
priority_queue<Degree>q;
for(int i=1;i<=n;i++)
if(in[i]>s.w)
{
s.w=in[i];
s.id=i;
}
q.push(s);vis[s.id]=1;
while(!q.empty())
{
Degree u=q.top();q.pop();
for(int i=head[u.id];~i;i=edge[i].next){
int e=edge[i].e;
if(!vis[e])
{
printf("%d %d\n",u.id,e);
in[e]--;
vis[e]=1;
q.push({in[e],e});
}
}
}
} 14.LCA树上两点最近公共祖先(倍增)
int deep[maxn];//树的深度
int f[maxn][30];//fa[i][j] 节点i的2^j次方的祖先
void dfs(int u,int fa)//预处理深度 与祖先的关系
{
deep[u]=deep[fa]+1;
f[u][0]=fa;
for(int i=1;(1<<i)<=deep[u];i++)//不加限制也行
f[u][i]=f[f[u][i-1]][i-1];//2^i = 2^(i-1)+2^(i-1)
for(int i=head[u];~i;i=edge[i].next){
int e=edge[i].e;
if(e!=fa) dfs(e,u);
}
}
int LCA(int u,int v)
{
if(deep[u]<deep[v]) swap(u,v);//保持u比v深
for(int i=25;i>=0;i--) if(deep[f[u][i]]>=deep[v]) u=f[u][i];//比他深往上跳
if(u==v) return u;
for(int i=25;i>=0;i--){
if(f[u][i]!=f[v][i]){//因为从同一深度开始向上跳 一样有可能是更远的祖先
u=f[u][i];
v=f[v][i];
}
}
return f[u][0];//随便返回一个上一级即可
}
/***
主函数调动
dfs(p,p) // p为根节点 选择不同的根可能会造成不同的结果
***/ 15.树上两点最近公共祖先 Tarjan
int head[maxn],qhead[maxn];//保存原图 与 询问图
struct node{
int e,next;
int lca;
}edge[maxn],qedge[maxn];//保存原图 与 询问图
int fa[maxn];//与并查集类似，回溯时更新
int vis[maxn];//标记点是否访问过
ll cnt=0,cnt1=0;
/****
存图过程省略
****/
int Find(int x)//找爹函数 类似并查集
{
return x==fa[x]?x:fa[x]=Find(fa[x]);
}
void dfs(int u)
{
fa[u]=u;//起初每一个节点的父亲都设为自己
vis[u]=1;//已被搜索过
for(int i=head[u];~i;i=edge[i].next)
{
int e=edge[i].e;
if(!vis[e]){
dfs(e);
fa[e]=u;
}
}
for(int i=qhead[u];~i;i=qedge[i].next)//回溯时处理
{
int e=qedge[i].e;
if(vis[e]){
if(i%2) qedge[i].lca=qedge[i-1].lca=Find(e);
else qedge[i].lca=qedge[i+1].lca=Find(e);
}
}
} 16.Tarjan算法求割点
ll cnt=0,ans=0;
int res[maxn];//储存割点
int dfn[maxn],low[maxn],cot=0;//当前DFS顺序，可到最短顺序标号
map<int,int>mp;//判重 n很小数组就可以 map省空间
void Tarjan_min(int u,int fa)
{
dfn[u]=low[u]=++cot;
int child=0;
for(int i=head[u];~i;i=edge[i].next)
{
int e=edge[i].e;
if(!dfn[e])
{
child++;
Tarjan_min(e,u);
low[u]=min(low[u],low[e]);
if(fa==-1&&child>=2&&!mp[u]){
res[++ans]=u;
mp[u]=1;
}
if(fa!=-1&&low[e]>=dfn[u]&&!mp[u]){
res[++ans]=u;
mp[u]=1;
}
}
else if(e!=fa)//父边
low[u]=min(low[u],dfn[e]);//必须为dfn[e] 例：1-2 2-3 3-4 4-3 3-1 3为割点
}
}
/***主函数中调用 考虑到图不连通的情况
for(int i=1;i<=n;i++)
if(!dfn[i])
Tarjan_min(i,-1);
***/
17.Floyd最小环及路径还原：
int mat[N][N], dist[N][N];
int next[N][N]; // next[i][j]表示ｉ到ｊ经历的第一个点。
int path[N];
int cnt, n;
void Floyd()
{
int mins=INF;
for(int k=1; k<=n; k++)
{
for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++)
{
int tmp = dist[i][j]+mat[i][k]+mat[k][j];
if(tmp < mins)// 更新最小环的权值
{
mins = tmp;
cnt=0;
int p = i;
while(p!=j) // 记录最小环的路径
{
path[cnt++] = p;
p = next[p][j];
}
path[cnt++] = j;
path[cnt++] = k;
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(dist[i][k]+dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
}
if(mins==INF)
puts("No solution.");
else
{
for(int i=0; i<cnt; i++)
printf("%d%s", path[i], i==cnt-1 ? "\n":" ");
}
} 18.欧拉回路及其还原
/***
存在欧拉回路需要判断：
1.图必须联通
2.无向图：所有点的度数均为偶数
有向图：所有点的入度等于出度
***/
int head[maxn];
int path[maxn],ans=0;//边路径
int N[maxn],cot=0;//点路径
int vis[maxn];//标记每条边被访问
ll cnt=0;
struct node{
int e,next,id;//为每条边进行标号
}edge[maxn];
void addedge(int u,int v,int id)
{
edge[cnt]=node{v,head[u],id};
head[u]=cnt++;
edge[cnt]=node{u,head[v],id};
head[v]=cnt++;
}
void Search(int u)
{
for(int i=head[u];~i;i=edge[i].next)
{
if(!vis[i]){
vis[i]=1;
Search(edge[i].e);
path[++ans]=i;//要么连着起点，要么连着与起点相连的边
N[++cot]=u;
}
}
}
/***
主函数：
N[++cot]=s;//s为起点
Search(s);
***/ Others Continue...
京公网安备 11010502036488号