图论
授课 zhx
最小生成树
最小生成树包括两个算法:
- kruskal
- Prim
两类算法均为基础知识，故不在讲解
严格次小生成树
对于一张有$n$个点$m$条边的无向图，我们要求去掉在去掉一条边的情况下求其最小生成树
也就是说：如果最小生成树选择的边集是$E_M$，严格次小生成树选择的边集是$E_S$，那么需要满足：($value(e)$表示边$e$的权值) (sum_{e∈E_M}value(e) < sum_{e∈E_S}value(e))
1°朴素 O(mnlogn)
首先我们先对原图建出最小生成树，然后依次枚举删除哪一条边，再对原图求最小生成树
2°倍增求LCA O(nlogn)
首先先对原图求出最小生成树，然后依次枚举非树边，求其LCA路径上的最大值与严格次大值，然后再与正在枚举的边的权值计算出值。取历次最小值
3°并查集
此方法复杂度可达到线性程度，并且要比倍增更加好写
但是……我不会
P4018 严格次小生成树
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const long long maxn=1e5+5;
struct node{
long long x;
long long y;
long long zh;
}a[3*maxn];
#define INF 2147483647000000
long long fa[maxn];
long long f[maxn][30],g[maxn][33],h[maxn][33];
long long depth[maxn];
bool b[3*maxn];
bool vis[3*maxn];
long long head[3*maxn],next[3*maxn],ver[3*maxn],edge[3*maxn];
long long tot,n,m;
inline void add(long long x,long long y,long long z)
{
ver[++tot]=y;
edge[tot]=z;
next[tot]=head[x];
head[x]=tot;
}
inline bool cmp(node a,node b)
{
return a.zh < b.zh;
}
inline long long findd(long long x)
{
if(fa[x] != x) fa[x]=findd(fa[x]);
return fa[x];
}
inline void unite(long long x,long long y)
{
long long r1=findd(x);
long long r2=findd(y);
if(r1 != r2) fa[r1]=r2;
}
inline void dfs(long long now,long long father)
{
for(long long i=head[now];i;i=next[i])
{
long long v=ver[i],val=edge[i];
if(depth[v]) continue;
if(v == father) continue;
depth[v] = depth[now]+1;
f[v][0] = now;
g[v][0] = val;
h[v][0] = 0;
for(long long j=1; j<=25 ; j++)
{
f[v][j] = f[f[v][j-1]][j-1];
if(g[v][j-1]<g[f[v][j-1]][j-1])
{
g[v][j] = g[f[v][j-1]][j-1];
h[v][j] = max(h[f[v][j-1]][j-1] , g[v][j-1]);
}
if(g[v][j-1]>g[f[v][j-1]][j-1])
{
g[v][j] = g[v][j-1];
h[v][j] = max(h[v][j-1] , g[f[v][j-1]][j-1]);
}
if(g[v][j-1] == g[f[v][j-1]][j-1])
{
g[v][j] = g[v][j-1];
h[v][j] = max(h[v][j-1] , h[f[v][j-1]][j-1]);
}
}
dfs(v,now);
}
}
inline long long get_maxx(long long p1,long long p2,long long &ans,long long &cnt)
{
ans = -INF;
cnt = -INF;
if(depth[p1] < depth[p2] )
{
p1=p1^p2;
p2=p1^p2;
p1=p1^p2;
}
for(long long i=25;i>=0;i--)
{
if(depth[f[p1][i]] >= depth[p2])
{
int ul=max(g[p1][i],cnt);
if(g[p1][i] != ul)
{
ans=max(g[p1][i],ans);
}
if(h[p1][i] != ul)
{
ans=max(h[p1][i],ans);
}
if(ans != ul)
{
ans=max(ans,ans);
}
if(cnt != ul)
{
ans=max(cnt,ans);
}
cnt=ul;
p1=f[p1][i];
}
}
if(p1 == p2) return ans;
for(long long i=25;i>=0;i--)
{
if(f[p1][i] != f[p2][i])
{
int ul=max(g[p1][i],cnt);
if(g[p1][i] != ul)
{
ans=max(g[p1][i],ans);
}
if(h[p1][i] != ul)
{
ans=max(h[p1][i],ans);
}
if(ans != ul)
{
ans=max(ans,ans);
}
if(cnt != ul)
{
ans=max(cnt,ans);
}
cnt=ul;
ul=max(g[p2][i],cnt);
if(g[p2][i] != ul)
{
ans=max(g[p2][i],ans);
}
if(h[p2][i] != ul)
{
ans=max(h[p2][i],ans);
}
if(ans != ul)
{
ans=max(ans,ans);
}
if(cnt != ul)
{
ans=max(cnt,ans);
}
cnt=ul;
p1=f[p1][i];
p2=f[p2][i];
}
}
long long s=min(g[p1][0],g[p2][0]);
long long t=max(g[p1][0],g[p2][0]);
int ul=max(t,cnt);
if(t != ul)
{
ans=max(t,ans);
}
if(s != ul)
{
ans=max(s,ans);
}
if(ans != ul)
{
ans=max(ans,ans);
}
if(cnt != ul)
{
ans=max(cnt,ans);
}
cnt=ul;
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin>>n>>m;
for(long long i=1,x,y,z;i<=m;i++)
{
cin>>x>>y>>z;
a[i].x =x;
a[i].y =y;
a[i].zh =z;
}
sort(a+1,a+1+m,cmp);
long long o;
for(int i=1;i<=n;i++)
fa[i]=i;
long long k=0,as,sum=0,spite=0;
for(int i=1;i<=m;i++)
{
long long v=a[i].x,u=a[i].y;
if(findd(v) != findd(u))
{
unite(u,v);
k++;
b[i]=1;
sum+=a[i].zh ;
add(u,v,a[i].zh );
add(v,u,a[i].zh );
o=u;
}
if(k ==n-1) break;
}
depth[o]=1;
dfs(o,0);
spite=INF;
for(int i=1;i<=m;i++)
{
if(b[i] == 0)
{
long long cnt,ans;
get_maxx(a[i].x,a[i].y,ans,cnt);
if(sum-ans+a[i].zh != sum)
{
spite=min(spite,sum-ans+a[i].zh);
}
if(sum-cnt+a[i].zh != sum)
{
spite=min(spite,sum-cnt+a[i].zh);
}
}
}
cout<<spite;
}
我直接裂开
最短路
对于最短路算法，熟练掌握一下三种方法
Floyd (全源最短路) O((n^3))
Dijstra + heap优化 (单源最短路,不可处理负边权) O((nlogn))
SPFA (单源最短路,允许存在负边权) O((kE))
差分约束
对于如下不等式
据观察，它们和我们的最短路$dis[u] ≤ dis[u]+s_{<u,v>}$三角形不等式很像
所以我们考虑建图，对每一个不等式，建一个从$i$到$j$的路径为权值$w_{<i,j>}$，然后跑一遍 如果不等式组无解，那么
先上代码：
P5960
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
int n,m;
bool inque[maxn];
int in[maxn];
int dis[maxn];
int head[maxn],next[maxn],edge[maxn],ver[maxn];
int tot;
inline void add(int x,int y,int z)
{
ver[++tot] = y;
edge[tot] = z;
next[tot] = head[x];
head[x] = tot;
}
inline bool spfa(int o)
{
memset(dis,0x3f,sizeof(dis));
memset(inque,0,sizeof(inque));
memset(in,0,sizeof(in));
queue<int> q;
dis[o]=0;
inque[o]=1;
in[o]=1;
q.push(o);
while(q.size())
{
int aux=q.front();
q.pop();
inque[aux]=0;
for(int i=head[aux];i;i=next[i])
{
if(dis[ver[i]] > dis[aux] + edge[i] )
{
dis[ver[i]]=dis[aux] + edge[i];
if(inque[ver[i]] != 1)
{
q.push(ver[i]);
inque[ver[i]]=1;
in[ver[i]]++;
if(in[ver[i]] >= n+1)
return false;
}
}
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin>>n>>m;
for(int i=1,x,y,z;i<=n;i++)
{
cin>>x>>y>>z;
add(y,x,z);
}
for(int i=1;i<=n;i++)
{
add(0,i,0);
}
if(spfa(0) == false)
{
cout<<"NO";
}
else
{
for(int i=1;i<=n;i++)
cout<<dis[i]<<endl;
}
}