从最害怕的专题到最喜欢的专题……嗯果然多刷题是最有用的w
目录
- 存图
- 邻接矩阵
- 链式前向星
- vector
- 最短路
- SPFA（死了）
- Floyed
- 堆优化Dijkstra
- 最短路计数
- 严格次短路
- 分层图最短路
- 最小生成树
- Kruskal
- Prim
- Tarjan
- 强连通分量
- 缩点
- 桥
- 割点
- 离线LCA
- 倍增LCA
- 拓扑排序
- 树的直径
- dfs法
- dp法
- 差分约束
- 网络流
- 二分图匹配
- 最大流
- 费用流
- 负环
- 最小环
- 欧拉回路
一、存图
1、邻接矩阵存图
memset(mapp,128/3,sizeof mapp);
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
mapp[u][v]=mapp[v][u]=min(mapp[u][v],w);
}
2、链式前向星
struct sth{
int to,nxt,dis;
};
int tot,head[MAXN];
void add(int u,int v,int w){
a[++tot].to=v;a[tot].nxt=head[u];
a[tot].dis=w;head[u]=tot;
}
3、vector
vector<int>P[MAXN];
for(int i=1;i<=n;i++){
int u,v;
P[u].push_back(v);
P[v]=push_back(u);
}
以下内容均省去建图过程，一般是前向星存的。
二、最短路
1、SPFA （它曾活过啊）
void SPFA(){
queue<int>q;
memset(d,0x7f7f7f,sizeof d);
q.push(s);d[s]=0;vis[s]=1;
while(!q.empty()){
int noww=q.front();q.pop();
for(int j=head[noww];j;j=a[j].nxt){
int vv=a[j].to;
if(d[vv]>d[noww]+a[j].dis){
d[vv]=d[noww]+a[j].dis;
if(!vis[vv])q.push(vv),vis[vv]=1;
}
}vis[noww]=0;
}
}
2、Floyed
void Floyed(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(mapp[i][j]>mapp[i][k]+mapp[k][j])
mapp[i][j]=mapp[i][k]+mapp[k][j];
}
}
3、堆优化Dijkstra
struct node{
int to,dis;
bool operator <(const node &t) const{
return dis>t.dis;
}
}a[MAXM<<1];
priority_queue<node>q;
void dij(){
for(int i=1;i<=m;i++)d[i]=2147483647;
d[s]=0;node qwq;qwq.to=s;qwq.dis=0;
q.push(qwq);
while(!q.empty()){
node P=q.top();q.pop();
int noww=P.to;
if(visit[noww])continue;
visit[noww]=1;
for(int j=head[noww];j;j=nxt[j]){
int vv=a[j].to;
if(d[vv]>d[noww]+a[j].dis){
d[vv]=d[noww]+a[j].dis;
node qwq;qwq.to=vv;qwq.dis=d[vv];
q.push(qwq);
}
}
}
}
四、最短路计数
void SPFA(){
q.push(1);dis[1]=0;
t[1]=1;vis[1]=1;
while(!q.empty()){
int noww=q.front();q.pop();
if(noww==n)continue;//重要
for(int i=1;i<=n;i++){
if(dis[noww]+a[noww][i]==dis[i])
t[i]+=t[noww];
if(dis[noww]+a[noww][i]<dis[i]){
dis[i]=dis[noww]+a[noww][i];
t[i]=t[noww];
}
if(t[i]&&!vis[i])vis[i]=1,q.push(i);
}
t[noww]=0,vis[noww]=0;//重要
}
}
五、严格次短路
priority_queue<P,vector<P>,greater<P> >q;
void dij(){
for(int i=1;i<=n;i++)d1[i]=d2[i]=inf;
d1[1]=0;
q.push(P(1,0));
while(!q.empty()){
int noww=q.top().first;
int d=q.top().second;q.pop();
for(int j=head[noww];j;j=a[j].nxt){
int vv=a[j].to;int disv=a[j].dis+d;
if(disv<d1[vv]){
swap(d1[vv],disv);//重要
q.push(P(vv,d1[vv]));
}
if(disv>d1[vv]&&disv<d2[vv]){
d2[vv]=disv;
q.push(P(vv,d2[vv]));
}
}
}
}
六、分层图最短路
了解了算法就一眼能瞪出正解的题型...
建一个k+1层的图，层内连边，层之间连0边即可。（其实是dp思想）
#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int MAXM=6000005;
int n,m,k,tot,head[MAXN],s,t;
int d[MAXN];
struct sth{
int to,nxt,dis;
}a[MAXM];
struct node{
int qwq,diss;
bool operator <(const node& t)const{
return diss>t.diss;
}
};
priority_queue<node>q;
void add(int u,int v,int w){
a[++tot].dis=w;a[tot].to=v;
a[tot].nxt=head[u];head[u]=tot;
}
void dij(){
memset(d,128/3,sizeof d);d[s]=0;
node ss;ss.diss=0;ss.qwq=s;q.push(ss);
while(!q.empty()){
node noww=q.top();q.pop();
int nowq=noww.qwq;
for(int j=head[nowq];j;j=a[j].nxt){
int vv=a[j].to;
if(d[vv]>d[nowq]+a[j].dis){
d[vv]=d[nowq]+a[j].dis;
node orz;orz.qwq=vv;orz.diss=d[vv];
q.push(orz);
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&t);s++;t++;
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
u++;v++;
for(int j=0;j<=k;j++){
add(u+j*n,v+j*n,w);add(v+j*n,u+j*n,w);
if(j!=k){
add(u+j*n,v+(j+1)*n,0);
add(v+j*n,u+(j+1)*n,0);
}
}
}
for(int j=0;j<k;j++){
add(t+n*j,t+n*(j+1),0);
add(t+n*(j+1),t+n*j,0);
}
dij();
printf("%d
",d[t]);
return 0;
}
七、最小生成树
1、适合稀疏图的Kruskal
void qsort(int l,int r){
int i=l,j=r;node mid=a[(i+j)/2];
while(i<=j){
while(cmp(a[i],mid))i++;
while(cmp(mid,a[j]))j--;
if(i<=j){
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}
if(i<r)qsort(i,r);
if(l<j)qsort(l,j);
}
int findx(int x){return (x==fa[x])?fa[x]:fa[x]=findx(fa[x]);}
void solve(){
qsort(1,m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
if(findx(a[i].x)!=findx(a[i].y)){
ans+=a[i].w;
fa[findx(a[i].x)]=a[i].y;
p++;
if(p==n)return ;
}
}
}
2、适合稠密图的Prim
（都8012年了我才会Prim）
void Prim(){
for(int i=1;i<=n;i++){
mincost[i]=mapp[1][i];
}
use[1]=1;//重要
for(int i=1;i<n;i++){
int minn=99999999;
int j;
for(int k=1;k<=n;k++){
if(!use[k]&&mincost[k]<minn){
j=k;
minn=mincost[k];
}
}
use[j]=1;
ans+=minn;
for(int k=2;k<=n;k++){
if(!use[k]&&mincost[k]>mapp[j][k]){
mincost[k]=mapp[j][k];
}
}
}
}
八、Tarjan
1、强联通分量
int dfs(int x){
dfn[x]=low[x]=++cntt;
vis[x]=1;s.push(x);
for(int j=head[x];j;j=a[j].nxt){
int vv=a[j].to;
if(!dfn[vv]){
int lowv=dfs(vv);
low[x]=min(low[x],lowv);
}
else{
if(vis[vv]){
low[x]=min(low[x],low[vv]);
}
}
}
if(dfn[x]==low[x]){
cntcol++;colour[x]=cntcol;cnt[cntcol]++;
vis[x]=0;
sta[cntcol][1]=x;
while(s.top()!=x){
colour[s.top()]=cntcol;cnt[cntcol]++;
vis[s.top()]=0;sta[cntcol][cnt[cntcol]]=s.top();
s.pop();
}s.pop();
maxcnt=max(maxcnt,cnt[cntcol]);
}
return low[x];
}
void tarjan(){
for(int i=1;i<=n;i++){
if(!dfn[i])dfs(i);
}
}
2、缩点
int tarjan(int u){
dep++;vis[u]=1;
s.push(u);
int lowu=dep;dfn[u]=low[u]=dep;
for(int j=head[u];j;j=a[j].nxt){
int vv=a[j].to;
if(!dfn[vv]){
int lowv=tarjan(vv);
lowu=min(lowu,lowv);
}else{
if(vis[vv])
lowu=min(lowu,low[vv]);
}
}
low[u]=lowu;
if(low[u]==dfn[u]){
cnt++;
colour[u]=cnt;vis[u]=0;
newq[cnt]+=q[u];
while(s.top()!=u){
colour[s.top()]=cnt;
newq[cnt]+=q[s.top()];
vis[s.top()]=0;
s.pop();
}s.pop();
}
return lowu;
}
void work(){
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=m;i++)
if(colour[x[i]]!=colour[y[i]])add(colour[x[i]],colour[y[i]]);
}
3、割点
void tarjan(int u,int fa){
int ch=0;dep++;
dfn[u]=low[u]=dep;
for(int j=head[u];j;j=a[j].nxt){
int vv=a[j].to;
if(!dfn[vv]){
ch++;
tarjan(vv,u);
low[u]=min(low[u],low[vv]);
if(low[vv]>=dfn[u])iscut[u]=1;
}else{
if(vv!=fa&&dfn[vv]<dfn[u])
low[u]=min(low[u],low[vv]);
}
}
if(fa==-1&&ch==1)iscut[u]=0;
if(fa==-1&&ch>=2)iscut[u]=1;
}
void work(){
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,-1);
}
}
4、桥
void tarjan(int u,int fa){
int ch=0;dep++;
dfn[u]=low[u]=dep;
for(int j=head[u];j;j=a[j].nxt){
int vv=a[j].to;
if(!dfn[vv]){
ch++;
tarjan(vv,u);
low[u]=min(low[u],low[vv]);
if(dfn[u]<low[vv])printf("%d %d
",u,vv);
}else{
if(vv!=fa&&dfn[vv]<dfn[u])
low[u]=min(low[u],low[vv]);
}
}
}
void work(){
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,-1);
}
}
5、离线求LCA
#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
int n,m,root;
struct sth{
int nxt,to,lca;
}a[MAXN],b[MAXN];
int tot,toot,head[MAXN],head2[MAXN];
void add(int u,int v){
a[++tot].to=v;a[tot].nxt=head[u];
head[u]=tot;
}
void add2(int u,int v){
b[++toot].to=v;b[toot].nxt=head2[u];
head2[u]=toot;
}
bool vis[MAXN];
int fa[MAXN];
int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
void dfs(int x){
fa[x]=x;
vis[x]=1;
for(int j=head[x];j;j=a[j].nxt){
int vv=a[j].to;
if(!vis[vv]){
dfs(vv);
fa[vv]=x;
}
}
for(int j=head2[x];j;j=b[j].nxt){
int vv=b[j].to;
if(vis[vv]){
b[j].lca=find(vv);
if(j&1)
b[j+1].lca=b[j].lca;
else b[j-1].lca=b[j].lca;
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add2(u,v);add2(v,u);
}
dfs(root);
for(int i=1;i<=toot;i+=2)printf("%d
",b[i].lca);
return 0;
}
九、倍增求LCA
void dfs(int u,int f,int d){
fa[u][0]=f;deep[u]=d;
for(int i=head[u];i;i=a[i].nxt){
int vv=a[i].to;
if(vv!=f)dfs(vv,u,d+1);
}
}
int lca(int u,int v){
if(deep[u]>deep[v])swap(u,v);
for(int k=0;k<19;k++){
if(((deep[v]-deep[u])>>k)&1)v=fa[v][k];
}if(u==v)return u;
for(int k=18;k>=0;k--){
if(fa[v][k]!=fa[u][k]){
u=fa[u][k];v=fa[v][k];
}
}return fa[u][0];
}
void work(){
dfs(root,-1,0);
for(int k=0;k+1<19;k++){
for(int j=1;j<=n;j++)
if(fa[j][k]<0)fa[j][k+1]=-1;
else fa[j][k+1]=fa[fa[j][k]][k];
}
}
十、拓扑排序
void tuopu(){//不断找入度为0的点
for(int i=1;i<=n;i++)if(!rudu[i])q.push(i);
while(!q.empty()){
int noww=q.front();q.pop();
tp[++cnt]=noww;
for(int j=head[noww];j;j=a[j].nxt){
int vv=a[j].to;rudu[vv]--;
if(!rudu[vv])q.push(vv);
}
}if(cnt!=n){
printf("No Solution!
");return;
}
for(int i=1;i<=cnt;i++)printf("%d ",tp[i]);
printf("
");
}
十一、树的直径
“你知道吗，树的直径有两种求法。”
（好像还可以bfs求，然而我没写过）
1、两遍dfs求法
void dfs(int noww){
if(dis[noww]>maxn){
maxn=dis[noww];
t=noww;
}
vis[noww]=1;
for(int j=head[noww];j;j=a[j].nxt){
int vv=a[j].to;
if(!vis[vv]){
dis[vv]=dis[noww]+a[j].to;
dfs(vv);
}
}
}
void work(){
maxn=-99999999;
memset(vis,0,sizeof vis);
memset(dis,128/3,sizeof dis);
dis[1]=0;
dfs(1);
s=t;
maxn=-99999999;
memset(vis,0,sizeof vis);
memset(dis,128/3,sizeof dis);
dis[s]=0;
dfs(s);
}
2、dp求法
void dfs(int noww,int from) {
dp[noww][0]=0;dp[noww][1]=0;
for (int j=head[noww];j;j=a[j].nxt){
int vv=a[j].to;
if(vv!=from){
dfs(vv,i);
if (dp[vv][0]+a[j].dis>dp[i][0]){
dp[i][1]=dp[i][0];
dp[i][0]=dp[vv][0]+a[j].dis;
}
else if(dp[to[j]][0]+a[j].dis>dp[i][1])
dp[i][1]=dp[vv][0]+a[j].dis;
}
}
ans=max(ans,dp[i][0]+dp[i][1]);
}//dfs(1,-1);
十二、差分约束
差分约束并没有固定的模板，但有固定的套路——
将条件中的差值不等式转换成最短路松弛时的不等式即可。
以洛谷P3275糖果一题为例，将五种要求转化成连边，跑SPFA。
不能成立的条件是出现环。
这里给出建图和最短路部分
bool SPFA(){
vis[0]=1,q.push(0);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
if(tot[u]==n-1){cout<<-1;return 0;}
tot[u]++;
for(int i=head[u];i;i=a[i].nxt)
if(d[a[i].to]<d[u]+a[i].dis){
d[a[i].to]=d[u]+a[i].dis;
if(!vis[a[i].to])vis[a[i].to]=1,q.push(a[i].to);
}
}return 1;
}
void init(){
for(ll i=1;i<=k;i++){
ll opt,u,v;
cin>>opt>>u>>v;
if(opt==1){
add(u,v,0);add(v,u,0);
}
if(opt==2){
add(u,v,1);
if(u==v){
cout<<"-1";return 0;
}
}
if(opt==3){
add(v,u,0);
}
if(opt==4){
add(v,u,1);if(u==v){
cout<<"-1";return 0;
}
}
if(opt==5){
add(u,v,0);
}
}
for(ll i=n;i>=1;i--)add(0,i,1);
}
十三、网络流
1、二分图匹配
当然可以跑网络流，然而二分图匹配更好写。（算法名字我分不清....）
bool dfs(int x){
for(int j=1;j<=m;j++){
if(!mapp[x][j])continue;
if(use[j])continue;
use[j]=1;
if(!match[j]||dfs(match[j])){
match[j]=x;
return 1;
}
}
return 0;
}
void work(){
for(int i=1;i<=n;i++){
memset(use,0,sizeof use);
if(dfs(i))ans++;
}
}
2、最大流
int bfs(){
memset(deep,0,sizeof(deep));
queue<int>q;
deep[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=e[i].nxt){
if(e[i].dis&&!deep[e[i].to]){
deep[e[i].to]=deep[u]+1;
q.push(e[i].to);
}
}
}
if(deep[t])return 1;
return 0;
}
int dfs(int u,int d) {
if(u==t)return d;
for(int i=head[u];i!=-1;i=e[i].nxt){
if((deep[e[i].to]==deep[u]+1)&&(e[i].dis)){
int di=dfs(e[i].to,min(d,e[i].dis));
if(di){
e[i].dis-=di;
e[i^1].dis+=di;
return di;
}
}
}
return 0;
}
int dinic(){
int ret=0;
while(bfs())
while(int di=dfs(s,INF))
ret+=di;
return ret;
}
还有最大流最小割定理。我不会证也懒得copy了...
3、费用流
把最大流的bfs改成SPFA就好啦
int spfa(){
memset(d,0x7f,sizeof(d));
d[s]=0;vis[s]=1;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i;i=a[i].nxt){
int vv=a[i].to;
if(a[i].dis&&d[u]+a[i].cost<d[vv]){
d[vv]=d[u]+a[i].cost;
if(!vis[vv])vis[vv]=1,q.push(vv);
}
}
}
return d[t];
}
int dfs(const int u,const int f){
if(f==0||u==t)return f;
int ret=0;vis[u]=1;
for(int i=cur[u];i;i=a[i].nxt){
cur[u]=i;
int v=a[i].to;
if(d[v]!=d[u]+a[i].cost||!a[i].dis)continue;
if(!vis[v]){
int ans=dfs(v,min(f-ret,a[i].dis));
ret+=ans;
a[i].dis-=ans,a[i^1].dis+=ans;
mincost+=a[i].cost*ans;
}
}
vis[u]=0;
return ret;
}
void dinic(){
while(spfa()!=0x7f7f7f7f){
for(int i=1;i<=n;i++)cur[i]=head[i];
while(int x=dfs(s,0x7f7f7f7f)){
maxflow+=x;
if(mincost>=0x7f7f7f2b)return;
}
}
}
十四、负环
如果有一个点入队次数大于(n)，那么一定有负环
bool SPFA(int s){
queue<int>q;
memset(vis,0,sizeof vis);
memset(d,128/3,sizeof d);
d[s]=0;vis[s]=1;cnt[s]=1;q.push(s);
while(!q.empty()){
int noww=q.front();q.pop();vis[noww]=0;
for(int j=head[noww];j;j=a[j].nxt){
int vv=a[j].to;
if(d[vv]>d[noww]+a[j].dis){
d[vv]=d[noww]+a[j].dis;
cnt[vv]=cnt[noww]+1;
if(cnt[vv]>n)return 0;
if(!vis[vv])vis[vv]=1,q.push(vv);
}
}
}return 1;
}
十五、最小环
只见过一道求最小环的题，感觉很有意思，值得一做。（虽然这道题的精髓在于建图）
for(int k=1;k<=a;k++){
for(int i=1;i<=k-1;i++)
for(int j=i+1;j<=k-1;j++){
int tmp=qwq[i][j]+dis[i][k]+dis[k][j];
if(tmp<ans)ans=tmp;
}
for(int i=1;i<=a;i++)
for(int j=1;j<=a;j++){
if(qwq[i][j]>qwq[i][k]+qwq[k][j])
qwq[i][j]=qwq[i][k]+qwq[k][j];
}
}
正确性证明：在枚举环上的(ij)时，因为这两个点没有被(k)松弛过，所以必定不会经过(k)
十六、欧拉回路
void dfs(int x){
for (int i=1;i<=n;i++)
if (mapp[x][i]){
mapp[x][i]--;
mapp[i][x]--;
dfs(i);
}
S.push(x);
}
void work(){
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
mapp[u][v]++;
mapp[v][u]++;
b[u]++;b[v]++;
n=max(n,max(u,v));
}
s=1;int cnt=0;
for(int i=n;i>=1;i--)
if(b[i]&1)s=i,cnt++;
if(cnt&&cnt!=2){
printf("No Solution!
");
exit(0);
}
dfs(s);
}