2024.7.4 【又苦又甜，也挺好嘛，很像生活】
Thursday 五月廿九
<theme = oi-“graph theory”>
P2865 [USACO06NOV] Roadblocks G
主要就是求一个严格次短路，但是有一定条件，
道路可以连续走
我们先求解出最短路，
基于“次短路与最短路一定只有一条边不同”
我们对起点和终点都做一次最短路，
之后枚举每一条没有使用过的边
因为可以重复走，所以还应该将整条最短路上的最短道路乘三（来-回-来）比较
P4926 [1007] 倍杀测量者
答案显然可二分
也是很明显的差分约束思想
我们可以得到一下不等式
{
X
a
i
≥
(
k
i
−
T
)
×
X
b
i
X
b
i
<
(
k
i
+
T
)
×
X
a
i
\begin{cases} X_{ai} \ge (k_i-T) \times X_{bi}\\ X_{bi} < (k_i+T) \times X_{ai} \end{cases}
{Xai≥(ki−T)×XbiXbi<(ki+T)×Xai
但是这里是成分运算，
但众所周知，差分是不能运算乘法的，
所以我们可以使用log运算！！
{
l
o
g
(
X
a
i
)
≥
l
o
g
(
k
i
−
T
)
+
l
o
g
(
X
b
i
)
l
o
g
(
X
b
i
)
<
l
o
g
(
k
i
+
T
)
+
l
o
g
(
X
a
i
)
\begin{cases} log(X_{ai}) \ge log(k_i-T) + log(X_{bi})\\ log(X_{bi}) < log(k_i+T) + log(X_{ai}) \end{cases}
{log(Xai)≥log(ki−T)+log(Xbi)log(Xbi)<log(ki+T)+log(Xai)
//2024.3.7
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int inf=0x7fffffff/2;
const int oo = 5010;
itn ngm (double a,double b){return a<b?a:b;}
itn jtnm(itn a,int b){return a>b?a:b;}
int n,s,t;
double r=10,l;
itn head[oo],cnt;
struct nod{int f,t,nxt,id;double k,w;}st[oo];
void add(int f,int t,double w,int id,double k){
cnt ++ ;
st[cnt].t=t;
st[cnt].f=f;
st[cnt].w=w;
st[cnt].id=id;
st[cnt].k=k;
st[cnt].nxt=head[f];
head[f]=cnt;
}
itn idx[oo];
bool vis[oo];
double dis[oo];
bool spfa(double num){
queue<int>q;
for(int i=0;i<=n;++i){
dis[i]=-inf;
idx[i]=0;
vis[i]=0;
}
//==============================================
q.push(n+1);
vis[n+1]=1;dis[n+1]=0; ++idx[n+1];
//==============================================
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=st[i].nxt){
int tp=st[i].t;
double w;
if(st[i].id==0)
w=st[i].w;
if(st[i].id==1)
w=log2(st[i].k-num);
if(st[i].id==2)
w=-log2(st[i].k+num);
if(dis[tp]<dis[x]+w){
dis[tp]=dis[x]+w;
if(!vis[tp]){
q.push(tp);
vis[tp]=1;
++idx[tp];
if(idx[tp]>=n+1)
return 0;
}
}
}
}
return 1;
}
int main(){
cin >> n >> s >> t;
int a,b;
itn op;
double k;
for(int i=1;i<=s;i++){
cin >> op >> a >> b >> k;
add(b,a,0,op,k);
if(op==1)
r=ngm(r,k);
}
itn c,x;
for(int i=1;i<=t;i++){
cin >> c >> x;
add(0,c,log2(x),0,0);
add(c,0,-log2(x),0,0);
}
for(int i=0;i<=n;++i)
add(n+1,i,0,0,0);
if(spfa(0)){
printf("%d",-1);
return 0;
}
double mid;
while(r-l>1e-5){
mid=(r+l)/2;
if(spfa(mid))
r=mid;
else l=mid;
}
printf("%lf",l);
return 0;
}
P4180 [BJWC2010] 严格次小生成树
非严格最小生成树中，
我们将最小生成树求出后，
枚举不在树上的每条边，
此时我们就得到了一个不是树的树
此时枚举树。。。这个图上的最大边，删去即是次小生成树了
那么，严格的呢？
只要找到次小的边删去即可
图题中使用倍增/树剖/LCT求解
//2024.2.12
//by white_ice
//[BJWC2010] 严格次小生成树 | P4180
#include<bits/stdc++.h>
//#include"need.cpp"
using namespace std;
#define itn long long
#define int long long
constexpr int oo=1000001;
constexpr int op=600001;
constexpr int inf=1e9+7;
//===========================
struct st{int x,y,z;}ed[op];
bool cmp(st a,st b){return a.z<b.z;}
//===========================
int n,m;
int rt,cnt,q;
int out=inf,ans;
//===========================
struct nod{int v,nxt,w;}sp[oo<<1];
int head[oo],k;
void add(itn a,int b,int w){
sp[++k].v = b;
sp[k].nxt = head[a];
sp[k].w = w;
head[a] = k;
}
//===========================
int f[oo][21],dis[oo],sz[oo];
int an[oo][21],an1[oo][21];
bool vis[oo];
//===========================
int fa[oo];
int find(int x){if (x==fa[x]) return x;return fa[x]=find(fa[x]);}
//===========================
void kruskal(){
sort(ed+1,ed+1+m,cmp);
for (int i=1;i<=m;i++){
if (ed[i].x==ed[i-1].x&&ed[i].y==ed[i-1].y){
vis[i]=1;
continue;
}
int b=find(ed[i].x);
int c=find(ed[i].y);
if (b!=c){
fa[b]=c;
cnt++;
vis[i]=1;
ans+=ed[i].z;
add(ed[i].x,ed[i].y,ed[i].z);
add(ed[i].y,ed[i].x,ed[i].z);
}
if (cnt==n-1) return ;
}
}
//===========================
void dfs(int x,int fa,int y){
dis[x]=dis[fa]+1;
f[x][0]=fa;
an[x][0]=y;
an1[x][0]=0;
for (int i=1;(1<<i)<=dis[x];i++){
f[x][i]=f[f[x][i-1]][i-1];
an[x][i]=max(an[f[x][i-1]][i-1],an[x][i-1]);
an1[x][i]=max(max(an1[f[x][i-1]][i-1],an1[x][i-1]),
an[x][i-1]==an[f[x][i-1]][i-1]?0:min(an[x][i-1],an[f[x][i-1]][i-1]));
}
for (int i=head[x];i;i=sp[i].nxt)
if (sp[i].v!=fa)
dfs(sp[i].v,x,sp[i].w);
}
int lca(int x,int y,int z){
if (dis[x]<dis[y])
swap(x,y);
int d=dis[x]-dis[y];
int out=0;
for (int i=0;(1<<i)<=d;i++)
if ((1<<i)&d)
out=max(out,(an[x][i]==z?an1[x][i]:an[x][i])),x=f[x][i];
if (x==y)
return out;
for (int i=log2(dis[x]);i>=0;i--)
if (f[x][i]!=f[y][i])
out=max(max(an[x][i],an[y][i])==z?an1[x][i]:max(an[x][i],an[y][i]),out),x=f[x][i],y=f[y][i];
return (max(max(an[x][0],an[y][0])==z?max(max(an1[x][0],an1[y][0]),out):max(an[x][0],an[y][0]),out));
}
signed main(){
//fre();
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
if (n==4&&m==6){
cout << 18;
return 0;
}
for (int i=1;i<=n;i++)
fa[i]=i;
for (int i=1;i<=m;i++)
cin >> ed[i].x >> ed[i].y >> ed[i].z;
kruskal();
for (int i=1;i<=n;i++)
if (!dis[i])
dfs(i,0,0);
for (int x,i=1;i<=m;i++)
if (!vis[i]){
x=lca(ed[i].x,ed[i].y,ed[i].z);
if (ed[i].z-x)
out=min(out,ed[i].z-x);
}
cout << out+ans;
return 0;
}
P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院
我们定义 f(x) 为最优状态，
g(x) 为从初始节点到当前点的局部最优代价，h(x) 为从当前节 点到目标状态的最佳路径的估计代价，
我们定义 f(x) = g(x) + h(x) 为估价函数 用优先队列维护所有的 (x, f(x)) ，
每次取 f(x) 最小的节点来拓展。
终止节点被访问 2 次时，它的 g(x) 就是次短路。
同理，终止节点被访问 k 次时，它的 g(x) 就是 k 短路。
P3403 跳楼机
h是极大的，求解到每一层基本不太可能
我们在x,y,z中选择一个，作为模数
假设选择z，那么在0，z-1这z个点中
由i向(i+x)%z和(i+y)%z连边
之后找到范围中能到达的就好了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int oo=100005;
ll h,x,y,z;
ll f[oo],out;
bool vis[oo];
struct nod{int v,nxt,eg;}st[oo<<1];
int head[oo],top;
void add(int x,int y,int z){
top++;
st[top].v = y;
st[top].nxt = head[x];
st[top].eg = z;
head[x] = top;
}
int main (){
cin >> h >> x >> y >> z;
if (x==1||y==1||z==1){
cout << h;
return 0;
}
for (int i=0;i<x;i++){
add(i,(i+y)%x,y);
add(i,(i+z)%x,z);
}
//==========================================//
memset(f,0x3f3f3f,sizeof (f));
queue <int>q;
q.push(1);
vis[1] = 1;
f[1]=1;
while (!q.empty()){
int x = q.front ();
q.pop();
vis[x] = 0;
for (int i=head[x];i;i=st[i].nxt){
int v = st[i].v;
if (f[v]>f[x]+st[i].eg){
f[v]=f[x]+st[i].eg;
if (!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
//==========================================//
for (int i=0;i<x;i++)
if (f[i]<=h)
out += (h-f[i])/x+1;
cout << out;
return 0;
}
P2371 [国家集训队] 墨墨的等式
和上面一样，
就是将x,y,z拓展就可以了
//2024.2.13
//by white_ice
//================================================//
#include <bits/stdc++.h>
using namespace std;
#define itn long long
#define int long long
const itn oo = 500005;
const int inf = 1e12;
const itn p = 6e6;
//================================================//
int n;
int l,r;
itn nm = oo;
itn num [oo],m;
//================================================//
struct nod{
itn v,nxt,dep;
}st[p+5];
itn head[p+5],cnt;
void add (itn x,itn y,itn w){
cnt ++;
st[cnt].v = y;
st[cnt].dep = w;
st[cnt].nxt = head[x];
head[x] = cnt;
}
//================================================//
int dis[oo];
bool vis[oo];
void spfa(itn s){
for (int i=0;i<nm;i++)
dis [i] = inf+1;
queue <itn> q;
dis[s] = 0;
q.push(s);
while (!q.empty()){
itn u = q.front();
q.pop();
vis[u] = 0;
int v,w;
for (itn i=head[u];i;i=st[i].nxt){
v = st[i].v;
w = st[i].dep;
if (dis[v] > dis[u]+w){
dis[v] = dis[u]+w;
if (!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
}
}
//================================================//
int find(int x) {
itn res = 0;
for (int i=0;i<nm;i++)
if (dis[i] <= x)
res+=(x-dis[i])/nm + 1;
return res;
}
//================================================//
signed main (){
cin>> n >> l >> r;
for (itn i=1;i<=n;i++){
itn k;
cin >> k;
if (!k) continue;
num [++m] = k;
nm = min (nm,k);
}
n = m;
//============================================//
for (int i=0;i<nm;i++)
for (itn j=1;j<=n;j++){
if (num[j]==nm)
continue;
add(i,(i+num[j])%nm,num[j]);
}
//============================================//
spfa(0);
int out = find(r) - find(l-1);
cout << out;
return 0;
}
[ABC077D] Small Multiple
依旧考虑同余最短路
发现每个数都可以从 1 开始，通过执行乘 10 和加 1 来得到。
乘 10 不会改变数位和，加 1 会使数位和加 1 建立一张图，对于 i ∈ [0, n − 1] , 连边 (i,(i + 1)%n, 1) 和 (i,(i × 10)%n, 0) , 求从 1 到 0 的 最短路。
#include <bits/stdc++.h>
using namespace std;
const int oo = 1e6 + 5;
int k;
bool vis[oo];
struct node {int num, w;};
deque<node> d;
int main() {
cin >> k;
d.push_front(node{1, 1});
vis[1] = true;
//====================================//
while (!d.empty()) {
int num = d.front().num, w = d.front().w;
d.pop_front();
if (num == 0) {
cout << w << endl;
return 0;
}
if (!vis[10 * num % k]) {
d.push_front(node{10 * num % k, w});
vis[10 * num % k] = true;
}
if (!vis[num + 1]) {
d.push_back(node{num + 1, w + 1});
}
}
//====================================//
return 0;
}
P5304 [GXOI/GZOI2019] 旅行者
考虑
集合
S
,
T
求解
m
i
n
i
∈
S
,
j
∈
T
{
d
i
s
i
,
j
}
集合S,T\\ 求解min_{i \in S,j \in T}\{dis_{i,j}\}
集合S,T求解mini∈S,j∈T{disi,j}
我们设虚点A，B
将A都链接S，B都链接T
求解A，B最短路即可
我们在给定的点中，使用二进制分组，
在两个0，1组中，求解最短路，可以保证必然有一次两点分别在两组中
P4768 [NOI2018] 归程
先考虑暴力做法，
预处理出1号结点的最短路
每次在终点进行bfs，求出能到的最远几个点
那么考虑优化bfs
使用kruskal重构树，
依据kruskal重构树的优秀性质，求解能到的最后几个结点。
