17做网站广州沙河,网站怎么做后台,建设标准下载网站,专业的模板建站企业题目1#xff1a;
给定一个n个点m条边的连通图#xff0c;保证没有自环和重边。对于每条边求出,在其他边权值不变的情况下,它能取的最大权值#xff0c;使得这条边在连通图的所有最小生成树上。假如最大权值为无限大#xff0c;则输出-1。
题解#xff1a;
先求出图的一…题目1
给定一个n个点m条边的连通图保证没有自环和重边。对于每条边求出,在其他边权值不变的情况下,它能取的最大权值使得这条边在连通图的所有最小生成树上。假如最大权值为无限大则输出-1。
题解
先求出图的一棵最小生成树
对于不在树上的边(x,y) 它的权值只要小于树上x到y路径中任意一条边就可以代替这条边。
对于在树上的边(x,y)可以先预处理出所有两端在x到y路径上的不在树上的边的最小值。它的权值一定要小于最小值。
路径max和min都可以用倍增求。 时间复杂度O(nlogn)
#includebits/stdc.h
using namespace std;
const int N2e55;
inline int read(){int x0,f1;char chgetchar();while(!isdigit(ch)){if(ch-)f-1;chgetchar();}while(isdigit(ch)){xx*10ch-0;chgetchar();} return x*f;
}
int n,m,cnt0,head[N];
int vis[N],ans[N];
int fa[N],dep[N],id[N];
int f[N][20],maxn[N][20];
struct data{int x,y,dis,id;
}a[N];
struct Edge{int v,w,nxt,id;
}edge[N1];
void add_edge(int u,int v,int w,int id){edge[cnt].vv;edge[cnt].ww;edge[cnt].idid;edge[cnt].nxthead[u];head[u]cnt;
}
int find(int x){if(fa[x]x) return fa[x];else return fa[x]find(fa[x]);
}
bool cmp(data a,data b){return a.disb.dis;
}
void build(){sort(a1,am1,cmp);for(int i1;in;i) fa[i]i;for(int i1;im;i){int xa[i].x;int ya[i].y;if(find(x)!find(y)){fa[find(x)]find(y);vis[a[i].id]1;add_edge(x,y,a[i].dis,a[i].id);add_edge(y,x,a[i].dis,a[i].id);}}
}
void dfs(int u){for(int i1;i18;i){f[u][i]f[f[u][i-1]][i-1];maxn[u][i]max(maxn[u][i-1],maxn[f[u][i-1]][i-1]);}for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;int wedge[i].w;if(vf[u][0]) continue;dep[v]dep[u]1;id[v]edge[i].id;f[v][0]u;maxn[v][0]w;dfs(v);}
}
void solve(int x,int y,int dis){xfind(x);while(dep[x]dep[y]){ans[id[x]]min(ans[id[x]],dis-1);int kfind(f[x][0]);fa[x]k;xfind(x);}//加入新的非树边出现环要把新出现的环缩成点
}
int get(int x,int y,int lca){int ans0;if(dep[x]dep[y]) swap(x,y);for(int i18;i0;i--)if(dep[f[x][i]]dep[y]){ansmax(ans,maxn[x][i]);xf[x][i];}if(xy){lcax;return ans;}for(int i18;i0;i--){if(f[x][i]!f[y][i]){ansmax(ans,maxn[x][i]);ansmax(ans,maxn[y][i]);xf[x][i],yf[y][i];}}lcaf[x][0];return max(ans,max(maxn[x][0],maxn[y][0]));
}
int main(){nread();mread();for(int i1;im;i){a[i].xread();a[i].yread();a[i].disread();ans[i]2e9; a[i].idi;}build();dfs(1);for(int i1;in;i) fa[i]i;for(int i1;im;i){if(!vis[a[i].id]){int xa[i].x,ya[i].y,z;ans[a[i].id]get(x,y,z)-1;solve(x,z,a[i].dis);solve(y,z,a[i].dis);}}for(int i1;im;i){if(ans[i]2e9) printf(-1 );else printf(%d ,ans[i]);}
}题目2
题解
题目的操作其实可以看成给一条边权值加一
(u[lab],v[lab])这条边会被算到最小生成树里面只有在权值小于等于它的边加完后u[lab]和v[lab]不在一个连通块内。 我们把权值小于等于l[lab]的图建出来现在问题变成你可以用l[lab]−l[i]1的代价砍掉一些边使得u[lab]和v[lab]不连通最小割就好了。
题目3
给定一个有n个点m条边的无向连通图每条边有边权。 定义一次操作为选择一条图中的边并将其权值1。
试求最小的操作次数使得操作后的图的最小生成树是唯一的。
题解
