【做題記錄】圖論相關問題
A. 牛場圍欄
首先判斷 -1 的情況。
- 如果可用的長度中有 \(1\)，那么所有長度都能拼出來。
- 如果所有可用長度的 \(gcd\) 不為 \(1\)，那一定沒有最大值。
- 證明：設 \(gcd\) 為 \(q\)，則 \(q\mid x_1a_1+x_2a_2+\dots+x_na_n,x_1,x_2,\dots,x_n\in\mathbb{Z}\)。那么對于不能被 \(q\) 整除的數，就一定拼不出來。
然后考慮最小的能拼出來的數，顯然就是最小的可用長度，記為 \(mina\)，考慮它的每個剩余系 \(K_i,i=0,1,\dots mina-1\)，因為有解，所以一定存在一個最小的能拼出來的 \(t_i=mina\times p+i\)，因為 \(mina\) 是最小的所以 \(p\) 一定大于 \(0\)。則對于 \(K_i\) 最大的拼不出來的數就是 \(t_i-mina\)。\(t_i\) 可用同余最短路來求，就是說每個 \(K_i\) 都是一個點，每個可用長度都是一條邊。使用樸素 Dijkstra，時間復雜度為 \(O(mina^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define gcd __gcd
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e3+5,inf=0x3f3f3f3f;
int n,m,a[maxn],mina=maxn,dis[maxn];
bool vis[maxn];
vector<pii> e[maxn];
il void wuj(){
int tmp=0;
for(int i=1;i<=3e3;i++){
if(vis[i]){
tmp=gcd(tmp,i);
}
}
if(tmp>1||vis[1]){
puts("-1");
exit(0);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i]);
for(int j=0;j<=min(m,a[i]);j++){
vis[a[i]-j]=1;
}
}
for(int i=1;i<3e3;i++){
if(vis[i]){
mina=i;
break;
}
}
wuj();
memset(dis,0x3f,sizeof dis);
for(int i=1;i<3e3;i++){
if(!vis[i]){
continue;
}
dis[i%mina]=min(dis[i%mina],i);
for(int j=0;j<mina;j++){
e[j].pb(mp((j+i)%mina,i));
}
}
memset(vis,0,sizeof vis);
for(int i=1,u,v,w,mind;i<=mina;i++){
mind=inf;
for(int j=0;j<mina;j++){
if(mind>dis[j]&&!vis[j]){
mind=dis[j],u=j;
}
}
vis[u]=1;
for(pii j:e[u]){
v=j.fir,w=j.sec;
if(!vis[v]&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
int ans=0;
for(int i=0;i<mina;i++){
ans=max(ans,dis[i]-mina);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
B. 「LNOI2014」LCA
將深度轉化，其實就是這個點到根的路徑上的點的個數。
對于每個詢問 \(l,r,u\)，將 \(\forall i\in[l,r]\) 到根都權值加一，再求 \(u\) 到根的權值和。樹剖 \(+\) 線段樹。
考慮離線，每個詢問在 \(l-1\) 處減，在 \(r\) 處加，從 \(1\) 到 \(n\) 掃一遍就行了。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define lid id<<1
#define rid id<<1|1
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e4+5,mod=201314;
int n,m,fa[maxn],ans[maxn];
int dfn[maxn],cnt;
int top[maxn],sz[maxn],hes[maxn];
vector<int> e[maxn];
vector<pii> hao[maxn];
il void dfs1(int u){
sz[u]=1;
int mxs=0;
for(int v:e[u]){
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v];
hes[u]=v;
}
}
}
il void dfs2(int u){
dfn[u]=++cnt;
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(int v:e[u]){
if(v!=hes[u]){
dfs2(v);
}
}
}
int sum[maxn<<2],tag[maxn<<2];
il void pushup(int id){
sum[id]=(sum[lid]+sum[rid])%mod;
}
il void pushtag(int id,int l,int r,int val){
(tag[id]+=val)%=mod;
(sum[id]+=(r-l+1)*val)%=mod;
}
il void pushdown(int id,int l,int r){
if(tag[id]){
int mid=(l+r)>>1;
pushtag(lid,l,mid,tag[id]);
pushtag(rid,mid+1,r,tag[id]);
tag[id]=0;
}
}
il void upd(int id,int L,int R,int l,int r,int val){
if(L>=l&&R<=r){
pushtag(id,L,R,val);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,val);
}
if(r>mid){
upd(rid,mid+1,R,l,r,val);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return sum[id];
}
pushdown(id,L,R);
int mid=(L+R)>>1,res=0;
if(l<=mid){
(res+=query(lid,L,mid,l,r))%=mod;
}
if(r>mid){
(res+=query(rid,mid+1,R,l,r))%=mod;
}
return res;
}
il void upd(int u,int val){
while(top[u]!=1){
upd(1,1,n,dfn[top[u]],dfn[u],val);
u=fa[top[u]];
}
upd(1,1,n,dfn[1],dfn[u],val);
}
il int query(int u){
int res=0;
while(top[u]!=1){
(res+=query(1,1,n,dfn[top[u]],dfn[u]))%=mod;
u=fa[top[u]];
}
return (res+query(1,1,n,dfn[1],dfn[u]))%mod;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(n)read(m);
for(int i=2;i<=n;i++){
read(fa[i]);
e[++fa[i]].pb(i);
}
dfs1(1),dfs2(1);
// for(int i=1;i<=n;i++){
// cout<<dfn[i]<<" ";
// }
// puts("");
for(int i=1,l,r,u;i<=m;i++){
read(l)read(r)read(u);
u++;
hao[l].pb(mp(-i,u)),hao[r+1].pb(mp(i,u));
}
for(int i=1;i<=n;i++){
upd(i,1);
for(pii j:hao[i]){
if(j.fir<0){
(ans[-j.fir]+=mod-query(j.sec))%=mod;
}
else{
(ans[j.fir]+=query(j.sec))%=mod;
}
}
}
for(int i=1;i<=m;i++){
printf("%lld\n",ans[i]);
}
return 0;
}
}
signed main(){return asbt::main();}
C. 跳跳棋
考慮每個狀態(tài) \((x,y,z),x<y<z\) 的轉移：
- \(y\) 移到左邊：\((2x-y,x,z)\)
- \(y\) 移到右邊：\((x,z,2z-y)\)
- \(x\) 移到中間：\((y,2y-x,z)\)
- \(z\) 移到中間：\((x,2y-z,y)\)
第 \(3\)、\(4\) 個轉移是矛盾的。具體地，設 \(d1=y-x\)，\(d2=z-y\)，若 \(d1<d2\) 則可以進行 第 \(3\) 個轉移，若 \(d1>d2\) 則可以進行第 \(4\) 個轉移，否則不可轉移。
我們令 \((x,y,z)\) 進行了 \(3\) 或 \(4\) 號操作后的狀態(tài)為它的父親。則它的父親可以通過第 \(1\) 或 \(2\) 個轉移到達它。則對于每一個狀態(tài)，可以找到它所屬的二叉樹。二叉樹的根就是那個 \(d1=d2\) 的狀態(tài)。而我們要求的就是兩個狀態(tài)在樹上的距離（如果所在的樹不一樣則無解）。
求樹上的距離的方式為求 \(lca\)。考慮如何去求。首先讓兩個狀態(tài)走到同一深度，然后二分 \(lca\) 的高度，判斷這個高度的祖先是否相同。
那么問題就在于如何快速求出某個狀態(tài)的深度與 \(k\) 級祖先了。我們考慮壓縮轉移。以第 \(3\) 個轉移為例，最多可以連續(xù)進行 \(\lfloor\frac{d2-1}{d1}\rfloor\) 次。設 \(tmp=\lfloor\frac{d2-1}{d1}\rfloor\)，\(tmp\) 次轉移后的狀態(tài)即為 \((x+tmp\times d1,y+tmp\times d2,z)\)。這樣我們最多跳 \(\log\max(d1,d2)\) 次。于是這兩個操作的時間復雜度就都是 \(\log\) 級別的了。因為還有個二分，最終的復雜度是 \(\log^2\) 的。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
struct node{
int a[3];
il void init(){
sort(a,a+3);
}
il int&operator[](int x){
return a[x];
}
il bool operator==(node x)const{
return a[0]==x[0]&&a[1]==x[1]&&a[2]==x[2];
}
il bool operator!=(node x)const{
return !(*this==x);
}
};
il int dep(node x){
int d1=x[1]-x[0],d2=x[2]-x[1];
int res=0;
while(d1!=d2){
if(d1>d2){
int tmp=(d1-1)/d2;
x[1]-=tmp*d2,x[2]-=tmp*d2;
res+=tmp;
}
else{
int tmp=(d2-1)/d1;
x[0]+=tmp*d1,x[1]+=tmp*d1;
res+=tmp;
}
d1=x[1]-x[0],d2=x[2]-x[1];
}
return res;
}
il node ganc(node x,int k){
int d1=x[1]-x[0],d2=x[2]-x[1];
while(k){
if(d1>d2){
int tmp=min((d1-1)/d2,k);
x[1]-=tmp*d2,x[2]-=tmp*d2;
k-=tmp;
}
else{
int tmp=min((d2-1)/d1,k);
x[0]+=tmp*d1,x[1]+=tmp*d1;
k-=tmp;
}
d1=x[1]-x[0],d2=x[2]-x[1];
}
return x;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
node p,q;
read(p[0])read(p[1])read(p[2]);
read(q[0])read(q[1])read(q[2]);
p.init(),q.init();
int dp=dep(p),dq=dep(q);
// cout<<dp<<" "<<dq<<"\n";
if(ganc(p,dp)!=ganc(q,dq)){
puts("NO");
return 0;
}
if(dp<dq){
swap(dp,dq),swap(p,q);
}
p=ganc(p,dp-dq);
int l=0,r=dq;
while(l<r){
int mid=(l+r)>>1;
if(ganc(p,mid)==ganc(q,mid)){
r=mid;
}
else{
l=mid+1;
}
}
puts("YES");
printf("%lld",dp-dq+l*2);
return 0;
}
}
signed main(){return asbt::main();}
D. Berland and the Shortest Paths
對圖進行 bfs，顯然這樣生成的樹是滿足要求的。
因此我們只需計算對于每個點，哪些邊是從上一層連下來的。所有點這個邊數的乘積就是總方案數。
輸出方案就對每一個點枚舉選哪條邊即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,m,tot,num[maxn];
int vis[maxn],dep[maxn];
vector<int> hao[maxn];
vector<pii> e[maxn];
queue<int> q;
il void dfs(int u){
if(u>n){
for(int i=1;i<=m;i++){
printf("%d",vis[i]);
}
puts("");
if(--tot==0){
exit(0);
}
return ;
}
for(int x:hao[u]){
vis[x]=1;
dfs(u+1);
vis[x]=0;
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m)read(tot);
for(int i=1,u,v;i<=m;i++){
read(u)read(v);
e[u].pb(mp(v,i));
e[v].pb(mp(u,i));
}
dep[1]=1,q.push(1);
while(q.size()){
int u=q.front();
q.pop();
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(!dep[v]){
dep[v]=dep[u]+1;
num[v]++,hao[v].pb(w);
q.push(v);
}
else if(dep[u]+1==dep[v]){
num[v]++,hao[v].pb(w);
}
}
}
ll res=1;
for(int i=2;i<=n;i++){
res*=num[i];
if(res>=tot){
break;
}
}
tot=min(tot*1ll,res);
printf("%d\n",tot);
dfs(2);
return 0;
}
}
int main(){return asbt::main();}
E. Breaking Good
首先 bfs 搞出最短路。
設最短路為 \(dep\)，本來完好的邊數為 \(sum\)，則對于一條最短路徑 \(i\)，設其中本來完好的邊數為 \(cnt\)，則答案為 \((dep-cnt)+(sum-cnt)\)。所以只需讓 \(cnt\) 最大。在 bfs 時轉移即可。題目還要求輸出方案，因此需要記錄路徑。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,enm,dep[maxn];
int cnt[maxn],hd[maxn],pre[maxn];
bool vis[maxn],zai[maxn],hp[maxn];
queue<int> q;
struct edge{
int v,w,id,nxt;
}e[maxn<<1];
il void addedge(int u,int v,int w,int id){
e[++enm]=(edge){v,w,id,hd[u]};
hd[u]=enm;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
int sum=0;
for(int i=1,u,v,w;i<=m;i++){
read(u)read(v)read(w);
addedge(u,v,w,i);
addedge(v,u,w,i);
sum+=w;
}
memset(cnt,-1,sizeof cnt);
cnt[1]=0;
vis[1]=1,q.push(1);
while(q.size()){
int u=q.front();
q.pop();
for(int i=hd[u],v,w;i;i=e[i].nxt){
v=e[i].v,w=e[i].w;
if(vis[v]&&dep[v]<=dep[u]){
continue;
}
if(!vis[v]){
dep[v]=dep[u]+1;
vis[v]=1,q.push(v);
}
if(cnt[v]<cnt[u]+w){
cnt[v]=cnt[u]+w;
pre[v]=u;
}
}
}
printf("%d\n",dep[n]+sum-2*cnt[n]);
// for(int i=1;i<=n;i++){
// cout<<pre[i]<<"\n";
// }
int u=n;
while(u!=1){
for(int i=hd[pre[u]],v,w,id;i;i=e[i].nxt){
v=e[i].v,w=e[i].w,id=e[i].id;
if(v==u){
zai[id]=1;
if(!w){
printf("%d %d %d\n",pre[u],u,1);
}
break;
}
}
u=pre[u];
}
for(u=1;u<=n;u++){
for(int i=hd[u],v,w,id;i;i=e[i].nxt){
v=e[i].v,w=e[i].w,id=e[i].id;
if(hp[id]){
continue;
}
hp[id]=1;
if(!zai[id]&&w){
printf("%d %d %d\n",u,v,0);
}
}
}
return 0;
}
}
int main(){return asbt::main();}
F. Turtle and Intersected Segments
對于三個能互相連邊的點 \((l_i,r_i,a_i),(l_j,r_j,a_j),(l_k,r_k,a_k)\)，其中 \(a_i\le a_j\le a_k\)，我們顯然只需要將 \(i\) 和 \(j\) 連邊，\(j\) 和 \(k\) 連邊就夠了。
于是進行掃描線，加入每個點時去找它的 \(a\) 值的前驅和后繼連邊。用 set 維護。
set::insert 的返回值為一個 pair，其中 first 為插入的這個值的迭代器，second 是一個 bool，表示有沒有插入成功（因為 set 去重）。類似地 multiset 只返回一個迭代器。
可以用 prev(it) 返回 \(it\) 的前一個迭代器，next 返回后一個。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define int ll
#define pb push_back
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+5;
int n,lsh[maxn<<1];
int fa[maxn],sz[maxn];
struct node{
int l,r,a;
}p[maxn];
vector<int> hao[maxn<<1];
struct cmp{
il bool operator()(const int &x,const int &y)const{
if(p[x].a==p[y].a){
return x>y;
}
return p[x].a<p[y].a;
}
};
set<int,cmp> hp;
struct edge{
int u,v,w;
il bool operator<(const edge &x)const{
return w<x.w;
}
}e[maxn<<1];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
il void solve(){
read(n);
int tot=0;
for(int i=1;i<=n;i++){
read(p[i].l)read(p[i].r)read(p[i].a);
lsh[++tot]=p[i].l;
lsh[++tot]=p[i].r;
}
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=n;i++){
hao[lwrb(lsh+1,lsh+tot+1,p[i].l)-lsh].pb(i);
hao[lwrb(lsh+1,lsh+tot+1,p[i].r)-lsh].pb(-i);
}
for(int i=1;i<=tot;i++){
sort(hao[i].begin(),hao[i].end(),greater<int>());
}
hp.clear();
int num=0;
for(int i=1;i<=tot;i++){
for(int u:hao[i]){
if(u<0){
hp.erase(-u);
continue;
}
auto tmp=hp.insert(u).first;
if(tmp!=hp.begin()){
e[++num]=(edge){*prev(tmp),u,p[u].a-p[*prev(tmp)].a};
}
if(next(tmp)!=hp.end()){
e[++num]=(edge){u,*next(tmp),p[*next(tmp)].a-p[u].a};
}
}
}
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
sort(e+1,e+num+1);
int cnt=0,ans=0;
for(int i=1;i<=num;i++){
if(find(e[i].u)!=find(e[i].v)){
merge(e[i].u,e[i].v);
cnt++,ans+=e[i].w;
}
}
printf("%lld\n",cnt==n-1?ans:-1);
for(int i=1;i<=tot;i++){
hao[i].clear();
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
int T;
read(T);
while(T--){
solve();
}
return 0;
}
}
signed main(){return asbt::main();}
G. MST Company
首先將所有與 \(1\) 相連的邊去掉，求一個最小生成森林。然后對于每個連通塊，從 \(1\) 向它連一條最小的邊。此時如果邊不夠或需要連的邊超出限制就無解。
然后去滿足 \(k\) 的限制。從沒有被選中的從 \(1\) 連出的邊中選一條連上，則要從形成的這個環(huán)上刪去一條邊（端點不能為 \(1\)）。顯然刪去最大的一條。設新連的邊為 \(w1\)，最大的邊為 \(w2\)，則要求 \(w1-w2\) 最小。每次 \(O(n)\) 掃一遍即可。總復雜度 \(O(nk)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,num,enm=1,hd[maxn];
int fa[maxn],sz[maxn];
vector<int> vec,ans;
struct edge{
int u,v,w,id,nxt;
il bool operator<(const edge &x)const{
return w<x.w;
}
}a[maxn],e[maxn];
il void addedge(int u,int v,int w,int id){
e[++enm].v=v;
e[enm].w=w;
e[enm].id=id;
e[enm].nxt=hd[u];
hd[u]=enm;
}
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
int mx[maxn];
bool ban[maxn],no[maxn];
il void dfs(int u,int fa){
// cout<<u<<"\n";
for(int i=hd[u],v;i;i=e[i].nxt){
v=e[i].v;
if(ban[i]||v==fa||v==1){
continue;
}
mx[v]=e[mx[u]].w>e[i].w?mx[u]:i;
dfs(v,u);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>num;
for(int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v>>a[i].w;
if(a[i].u>a[i].v){
swap(a[i].u,a[i].v);
}
a[i].id=i;
}
sort(a+1,a+m+1);
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
for(int i=1;i<=m;i++){
if(a[i].u==1){
continue;
}
if(find(a[i].u)!=find(a[i].v)){
merge(a[i].u,a[i].v);
addedge(a[i].u,a[i].v,a[i].w,a[i].id);
addedge(a[i].v,a[i].u,a[i].w,a[i].id);
ans.pb(a[i].id);
}
}
for(int i=1;i<=m;i++){
if(a[i].u==1){
if(find(a[i].u)==find(a[i].v)){
vec.pb(i);
}
else{
merge(a[i].u,a[i].v);
addedge(a[i].u,a[i].v,a[i].w,a[i].id);
addedge(a[i].v,a[i].u,a[i].w,a[i].id);
ans.pb(a[i].id);
num--;
}
}
}
if(num<0||num>vec.size()){
puts("-1");
return 0;
}
for(int i=1;i<n;i++){
if(find(i)!=find(i+1)){
puts("-1");
return 0;
}
}
for(int i=1;i<=num;i++){
// puts("666");
for(int j=1;j<=n;j++){
mx[j]=0;
}
for(int j=hd[1];j;j=e[j].nxt){
// cout<<e[j].v<<":\n";
dfs(e[j].v,1);
}
// for(int j=1;j<=n;j++){
// cout<<mx[j]<<" ";
// }
// cout<<"\n";
int mn=inf,tmp;
for(int j=0;j<vec.size();j++){
if(mn>a[vec[j]].w-e[mx[a[vec[j]].v]].w){
mn=a[vec[j]].w-e[mx[a[vec[j]].v]].w;
tmp=j;
}
}
// cout<<a[vec[tmp]].v<<"\n";
ban[mx[a[vec[tmp]].v]]=ban[mx[a[vec[tmp]].v]^1]=1;
no[e[mx[a[vec[tmp]].v]].id]=1;
// cout<<a[tmp].v<<"\n";
// cout<<a[mx[a[tmp].v]].id<<"\n";
addedge(a[vec[tmp]].u,a[vec[tmp]].v,a[vec[tmp]].w,a[vec[tmp]].id);
addedge(a[vec[tmp]].v,a[vec[tmp]].u,a[vec[tmp]].w,a[vec[tmp]].id);
ans.pb(a[vec[tmp]].id);
vec.erase(vec.begin()+tmp);
}
cout<<n-1<<"\n";
for(int i:ans){
if(!no[i]){
cout<<i<<" ";
}
}
return 0;
}
}
int main(){return asbt::main();}
H. DFS Trees
邊權互不相同，則最小生成樹只有一棵。
將最小生成樹邊打上標記，那么我們要求在以 \(i\) 點為根 dfs 時打上標記的邊成為樹邊。換句話說，要求沒被打上標記的邊成為返祖邊。
對于一條沒被標記的邊 \((u,v)\)，我們要求 dfs 時能走完它所在的環(huán)上其它的邊，設 \(dep_u<dep_v\)，考慮兩種情況：
- \(lca(u,v)=u\)，則只有根在 \(v\) 的子樹內或 \(u\) 對應 \(v\) 的兒子的子樹外時滿足。
- 否則，只有根在 \(u\) 或 \(v\) 的子樹中時才可滿足。
對于每條邊給能滿足的點權值加一，最后查詢每個點的權值是否為 \(m-(n-1)\) 就好了。可以用樹狀數組。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,cnt,anc[22][maxn];
int fa[maxn],sz[maxn],dep[maxn];
int top[maxn],dfn[maxn],hes[maxn];
bool vis[maxn];
pii a[maxn];
vector<pii> e[maxn];
struct dsu{
int fa[maxn],sz[maxn];
il void init(){
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
}
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
il bool check(int u,int v){
return find(u)==find(v);
}
}D;
il void dfs1(int u){
// cout<<u<<"\n";
anc[0][u]=fa[u];
for(int i=1;i<=20;i++){
anc[i][u]=anc[i-1][anc[i-1][u]];
}
dep[u]=dep[fa[u]]+1;
sz[u]=1;
int mxs=0;
for(pii i:e[u]){
int v=i.fir;
if(!vis[i.sec]||v==fa[u]){
continue;
}
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v];
hes[u]=v;
}
}
}
il void dfs2(int u){
dfn[u]=++cnt;
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(pii i:e[u]){
int v=i.fir;
if(!vis[i.sec]||v==fa[u]||v==hes[u]){
continue;
}
dfs2(v);
}
}
il int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
il int ganc(int u,int k){
int tmp=0;
while(k){
if(k&1){
u=anc[tmp][u];
}
k>>=1,tmp++;
}
return u;
}
struct fenwick{
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void upd(int pos,int val){
// cout<<pos<<"\n";
for(;pos<=n;pos+=lowbit(pos)){
tr[pos]+=val;
}
}
il int query(int pos){
int res=0;
for(;pos;pos-=lowbit(pos)){
res+=tr[pos];
}
return res;
}
}F;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1,u,v;i<=m;i++){
read(u)read(v);
a[i]=mp(u,v);
e[u].pb(mp(v,i));
e[v].pb(mp(u,i));
}
D.init();
for(int i=1;i<=m;i++){
if(!D.check(a[i].fir,a[i].sec)){
D.merge(a[i].fir,a[i].sec);
vis[i]=1;
}
}
// puts("666");
dfs1(1),dfs2(1);
// puts("777");
for(int i=1,u,v;i<=m;i++){
if(!vis[i]){
u=a[i].fir,v=a[i].sec;
if(dep[u]>dep[v]){
swap(u,v);
}
// cout<<u<<" "<<v<<"\n";
if(lca(u,v)==u){
F.upd(1,1);
u=ganc(v,dep[v]-dep[u]-1);
// puts("777");
F.upd(dfn[u],-1);
F.upd(dfn[u]+sz[u],1);
F.upd(dfn[v],1);
F.upd(dfn[v]+sz[v],-1);
}
else{
// puts("666");
F.upd(dfn[u],1);
// puts("777");
F.upd(dfn[u]+sz[u],-1);
// puts("888");
F.upd(dfn[v],1);
// puts("999");
F.upd(dfn[v]+sz[v],-1);
// puts("777");
}
}
}
for(int i=1;i<=n;i++){
printf("%d",F.query(dfn[i])==m-n+1);
}
return 0;
}
}
int main(){return asbt::main();}
I. The Shortest Statement
\(m-n\le20\)，則當我們搞出一棵生成樹時最多剩下 \(21\) 條邊。相應地會對答案產生改變的點最多有 \(42\) 個。對這些點跑 dijkstra 即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+25;
int n,m,q;
int fa[maxn],sz[maxn];
int dep[maxn],hes[maxn];
int top[maxn],tis[maxn];
int dis[50][maxn];
bool vis[maxn],viss[maxn];
vector<pii> e[maxn];
struct edge{
int u,v,w;
}a[maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(sz[u]>sz[v]){
sz[u]+=sz[v],fa[v]=u;
}
else{
sz[v]+=sz[u],fa[u]=v;
}
}
il void dfs1(int u){
dep[u]=dep[fa[u]]+1;
sz[u]=1;
int mxs=0;
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa[u]){
continue;
}
tis[v]=tis[u]+w;
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v];
hes[u]=v;
}
}
}
il void dfs2(int u){
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa[u]||v==hes[u]){
continue;
}
dfs2(v);
}
}
il int tdis(int u,int v){
int tu=u,tv=v;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
return tis[tu]+tis[tv]-tis[u]*2;
}
il void dijkstra(int s,int *dis){
priority_queue<pii> q;
memset(viss,0,sizeof viss);
dis[s]=0,q.push(mp(0,s));
while(q.size()){
int u=q.top().sec,v,w;
q.pop(),viss[u]=1;
for(pii i:e[u]){
v=i.fir,w=i.sec;
if(!viss[v]&&dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(mp(-dis[v],v));
}
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(n)read(m);
for(int i=1,u,v,w;i<=m;i++){
read(u)read(v)read(w);
a[i]=(edge){u,v,w};
}
for(int i=1;i<=n;i++){
fa[i]=i,sz[i]=1;
}
for(int i=1,u,v;i<=m;i++){
u=a[i].u,v=a[i].v;
if(find(u)!=find(v)){
merge(u,v);
e[u].pb(mp(v,a[i].w));
e[v].pb(mp(u,a[i].w));
}
else{
vis[a[i].u]=vis[a[i].v]=1;
}
}
memset(fa,0,sizeof fa);
dfs1(1),dfs2(1);
for(int i=1;i<=n;i++){
e[i].clear();
}
for(int i=1,u,v,w;i<=m;i++){
u=a[i].u,v=a[i].v,w=a[i].w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
memset(dis,0x3f,sizeof dis);
int tot=0;
for(int i=1;i<=n;i++){
if(vis[i]){
dijkstra(i,dis[++tot]);
}
}
read(q);
while(q--){
int u,v;
read(u)read(v);
int res=tdis(u,v);
for(int i=1;i<=tot;i++){
res=min(res,dis[i][u]+dis[i][v]);
}
printf("%lld\n",res);
}
return 0;
}
}
signed main(){return asbt::main();}
浙公網安備 33010602011771號