基础算法Prim/kruskal dij/spfa
$\text{Algorithm:}$
差分约束:
其他算法感觉都不需要写,就差分约束有时候容易建错图所以稍微记录一下
简述:
跑最短路,若A<=B+c,则从B->A连边长为C的边
跑最长路,若A<=B+c(也即B>=A+(-C)),则从A->B连边长为-C的边
对于连的边都为非负的差分约束,也即只有单向的条件,如 求至少的情况,只有“小于”和“不小于”的限制(A,B反过来自然可以)的情况下,可以使用tarjan缩点,具体做法见problems中的【银河】一题
额外解释:
求出最大值就是求出上限的最小值,跑最短路,建图根据此推。
求出至少的数就是求出下限的最大值,跑最长路,建图据此推出
差分约束可以理解为
A-B<=x
B-C<=y
则有式1+式2的A-C<=x+y
和图论有相同的传递性质,而最终答案取决于最小的约束,则是最短路。
而对于式子取反 B-A>=-x最终约束是最大约束,则有最长路
$\text{Problems:}$
Acwing 1146. 新的开始
乍看上去很难,仔细一想就没那么难了。首先可以发现联通肯定n-1条边与生成树有关,之后想办法转化点权。可以想到建立超级原点,跑0~n的最小生成树
Acwing 1145. 北极通讯网络
臭题,很简单其实我wa了几次特别弱智
#include<bits/stdc++.h>
#define db double
/*
有k个点相互之间可以不连边,在最小生成树中就等于有k-1条边不用练
显然在跑kruskal的时候不考虑最大的k-1条边就行了,也即输出第k大的边
*/
using namespace std;
const int N=510,inf=0x3f3f3f3f,eps=1e-4;
int n,m,k;
struct Nd{
db x,y;
}a[N];
struct edge{
int x,y;db w;
bool operator<(const edge &t) const{
return w<t.w;
}
}ed[N*N];
db get(int i,int j){
return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
int p[N];
int find(int x){
return x==p[x]?x:p[x]=find(p[x]);
}
signed main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++) ed[++m]={i,j,get(i,j)};
sort(ed+1,ed+m+1);int cnt=0;db res=0;
for(int i=1;i<=m;i++){
int x=ed[i].x,y=ed[i].y;
int pa=find(x),pb=find(y);
if(pa==pb) continue;
p[pa]=pb;cnt++;res=ed[i].w;
//n-1条边,第k大,也即第n-1-(k-1)=n-k小的
if(cnt==n-k) break;
}
printf("%.2lf",n==k?0:res);
return 0;
}
Acwing 346. 走廊泼水节
非常有意思的一道“构造题”。对于两个点集,点有a和b个,假设此时a,b内部已经成为完全图,两点集之间需要连接a*b个边,除去本来就有的一条边,连 $a\times b-1$ 条。考虑长度最小为 $w + 1$ (排除+反证法)。之后跑kruskal(等于逆向kruskal),同时按照上述方式统计就行,点集大小使用并查集附加sz即可。
同时要从小到大排序,不然无法保证正确性。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=6010;
int n,p[N],sz[N];
struct edge{
int x,y;ll w;
bool operator<(const edge& t)const{
return w<t.w;
}
}edges[N];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
signed main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);int m=0;
for(int i=1;i<n;i++){
int a,b;ll c;scanf("%d%d%lld",&a,&b,&c);
edges[++m]={a,b,c};
}
for(int i=1;i<=n;i++) p[i]=i,sz[i]=1;
sort(edges+1,edges+m+1);ll res=0;
for(int i=1;i<=m;i++){
int x=edges[i].x,y=edges[i].y;ll w=edges[i].w;
int pa=find(x),pb=find(y);
//这是等于在求最小生成树的时候进行的操作,必须从小到大排序,加的边权总和最小*(w+1)已经体现了
//如果从大到小,虽然res会更大,但不一定符合题意
res+=(sz[pa]*sz[pb]-1)*(w+1);
p[pa]=pb;sz[pb]+=sz[pa];
}
printf("%lld\n",res);
}
return 0;
}
Acwing 1148. 秘密的牛奶运输
严格次小生成树,方法就是y总视频的方法,无耻剽窃一下用作记录(y总的课讲的很好,肯定比看博客容易懂多了!)
跑最小生成树的时候建边,预处理出最小生成树上任两点之间最长和次长的距离,之后枚举非树边,如果大于最长就加上w减去最长,如果不大于最长那么就与次长进行比较。
因为如果加入一条边(长度w),生成树会出现一个环,这个环上其他点就是加入边的两个端点的路径。然后这个环上我们若取掉一个v,则答案为sum+w-v,我们为了保证严格次小要让w>v且v尽可能大,所以预处理任意两点简单路径的最大和次大边,之后按如上方法即可。
Luogu P4180 [BJWC2010] 严格次小生成树
上一题的升级版,必须在 $O(n \log n)$ 复杂度内完成
AcWing 368. 银河
所有东西都在链接里
made最后一个好像挺复杂,树上倍增要记录次小?这下不会了,弃疗