网站改版降权,西安烽盈网站建设推广,进入公众号后没有什么显示,互联网推广是什么工作内容题干#xff1a;
小p和他的朋友约定好去游乐场游玩#xff0c;但是他们到了游乐场后却互相找不到对方了。 游乐场可以看做是一张n个点#xff0c;m条道路的图#xff0c;每条道路有边权wi#xff0c;表示第一次经过该道路时的花费#xff08;第二次及以后经过时花费为…题干
小p和他的朋友约定好去游乐场游玩但是他们到了游乐场后却互相找不到对方了。 游乐场可以看做是一张n个点m条道路的图每条道路有边权wi表示第一次经过该道路时的花费第二次及以后经过时花费为0。 现在小p要去找他的朋友但他的朋友行踪很诡异小p总是要遍历完这n个点才能找到他同时小p希望总花费最小。 找到朋友的方案可能不唯一具体看样例解释小p想知道在这所有的方案中有多少条边在每个方案中都会被经过。
输入描述:
第一行两个整数n, m. p分别表示点数,边数,小p的初始位置。
接下来m行每行两个整数u, v, w表示从u到v有一条无向边边权为w。
输出描述:
输出一个整数k表示必须经过的边的数量。
示例1
输入
复制
5 7 1
1 2 3
2 3 7
1 3 5
2 4 2
1 5 3
5 4 3
2 5 3
输出
复制
2
说明 样例解释 几种可能的方案如下 1−2−4−5−4−2−1−31−2−4−5−4−2−1−3 1−5−4−2−4−5−1−31−5−4−2−4−5−1−3 1−3−1−2−5−2−41−3−1−2−5−2−4 1−2−5−2−4−2−5−2−4−2−5−2−4⋯−2−5−2−4−2−1−31−2−5−2−4−2−5−2−4−2−5−2−4⋯−2−5−2−4−2−1−3 可以证明4 - 2和1 - 3这两条边在所有方案中都被经过。 (以上每种方案的总花费均为13同时可以证明没有比这更优的策略)
示例2
输入
复制
3 3 1
1 2 1
1 3 1
2 3 2
输出
复制
2
示例3
输入
复制
3 3 1
1 2 2
2 3 2
1 3 2
输出
复制
0
备注: 2⩽nm⩽2∗105,1⩽边权⩽1062⩽nm⩽2∗105,1⩽边权⩽106
保证图联通保证无自环保证无重边
解题报告 好难的题不会证明但是倒是想明白了AC代码2那里为什么else if(i!(lstedge^1)) low[x]min(low[x],dfn[y]);这里不能写成 low[x]min(low[x],low[y]);因为你想啊虽然这个题能过。 按照这个边的顺序访问节点那么当访问边7的时候LOW[3]已经变成了2所以如果那样写那LOW[6]也变成了2.看起来是没什么问题但是我们看回溯到3这个节点的时候注意这时候还没访问3-6这条边刚刚那是6节点开始的6-3这条边他需要开始看能否把4节点这一支分出去当成一个子图了发现不行因为DFN[4]2这本是不对的但是托了3-2这条边优先访问的福啊就把状态弄成这样了然后再遍历3-6这个节点发现也不行因为DFN[6]2然后无奈返回并且不标记成是个割点但是很显然3这个点就是个割点这就是为什么板子要这么写
对于题目 AC代码
#includebits/stdc.h
using namespace std;
const int maxn200050;
int root,sum1,dfn[maxn],low[maxn],ans[maxn],f[maxn];
int getf(int u){return f[u]u?u:f[u]getf(f[u]);}
struct Ed{int u,v,w;bool operator(const Ed A)const{return wA.w;
}
}E[maxn];
struct Edge{int v,id,next;}e[maxn*2];
int first[maxn],tot;
void add(int u,int v,int id){e[tot].vv;e[tot].idid;e[tot].nextfirst[u];first[u]tot;
}
void tarjin(int u,int last){dfn[u]low[u]sum;for(int ifirst[u];~i;ie[i].next){int ve[i].v;if(i(1^last))continue;if(dfn[v]){low[u]min(low[u],dfn[v]);}else{tarjin(v,i);low[u]min(low[u],low[v]);if(low[v]dfn[u])ans[e[i].id]1;}}
}
int main(){int i,j,n,m,p,u,v,w;scanf(%d%d%*d,n,m);tot0;memset(first,-1,sizeof(first));for(i1;in;i)f[i]i;for(i0;im;i){scanf(%d%d%d,E[i].u,E[i].v,E[i].w);}sort(E,Em);for(i0;im;i){ji;while(j1mE[j1].wE[i].w)j;tot0;for(int ki;kj;k){int fugetf(E[k].u),fvgetf(E[k].v);if(fu!fv){add(fu,fv,k);add(fv,fu,k);}}for(int ki;kj;k){int fugetf(E[k].u),fvgetf(E[k].v);if(fufv || dfn[fu]) continue;tarjin(fu,-1);}for(int ki;kj;k){int fugetf(E[k].u),fvgetf(E[k].v);if(fufv)continue;first[fu]first[fv]-1;dfn[fu]dfn[fv]0;f[fu]fv;}ij;}int h0;for(i0;im;i)hans[i];couthendl;return 0;
}
AC代码2
#includebits/stdc.h
using namespace std;
#define maxn 200001
#define maxm 300001
struct edge
{int a,b,c;int id;inline void read(int _id){scanf(%d%d%d,a,b,c);id_id;}bool operator (const edge p)const{return cp.c;}
}e[maxm];
int n,m;
inline void init()
{int p;scanf(%d%d,n,m);scanf(%d,p);for(int i1;im;i) e[i].read(i);sort(e1,em1);
}
int head[maxn],nxt[maxm1],ver[maxm1],id[maxm1],tot;
inline void addedge(int a,int b,int _id)
{nxt[tot]head[a];ver[tot]b;id[tot]_id;head[a]tot;nxt[tot]head[b];ver[tot]a;id[tot]_id;head[b]tot;
}
int ans[maxm];int dfn[maxn],low[maxn],cnt;
inline void tarjan(int x,int lstedge)
{dfn[x]low[x]cnt;for(int ihead[x];i;inxt[i]){int yver[i];if(!dfn[y]){tarjan(y,i);low[x]min(low[x],low[y]);if(low[y]dfn[x]) ans[id[i]]666;}else if(i!(lstedge^1)) low[x]min(low[x],dfn[y]);}
}
int fa[maxn];inline int find(int x){return fa[x]x?x:fa[x]find(fa[x]);}
int main()
{init();for(int i1;in;i) fa[i]i;int Nowedge1;while(Nowedgem){int LNowedge,RNowedge;while(R1me[R].ce[R1].c) R;NowedgeR1;cnt0;tot1;for(int iL;iR;i){int afind(e[i].a),bfind(e[i].b);head[a]0;head[b]0;dfn[a]dfn[b]low[a]low[b]0;}for(int iL;iR;i){int afind(e[i].a),bfind(e[i].b);if(ab){ans[e[i].id]-1;continue;}ans[e[i].id]233;addedge(a,b,e[i].id);}for(int iL;iR;i){if(!dfn[find(e[i].a)]) tarjan(find(e[i].a),0);if(!dfn[find(e[i].b)]) tarjan(find(e[i].b),0);}for(int iL;iR;i) fa[find(e[i].a)]find(e[i].b);}int ttl 0;for(int i1;im;i){if(ans[i]666) ttl;}coutttlendl;return 0;
}
AC代码3
#includebits/stdc.h
using namespace std;
const int N2e510;
struct edge{int f,to,v;}a[N];
struct node{int to,id;};
bool cmp(edge a,edge b){return a.vb.v;}
int fa[N];vectornodeg[N];
int dfn[N],low[N],num;int ans[N];
int find(int x){return fa[x]x?x:fa[x]find(fa[x]);}
void unite(int x,int y){xfind(x),yfind(y),fa[x]y;}
void tarjan(int x,int fa){dfn[x]low[x]num;for(auto it:g[x]){int uit.to,idit.id;if(idfa) continue;if(!dfn[u]){tarjan(u,id);low[x]min(low[x],low[u]);if(dfn[x]low[u]) ans[id]1;}else low[x]min(low[x],dfn[u]);}
}
int main(){int n,m,q,x,y,c;scanf(%d%d%d,n,m,q);for(int i1;im;i) scanf(%d%d%d,a[i].f,a[i].to,a[i].v);sort(a1,am1,cmp);for(int i1;in;i) fa[i]i;for(int i1;im;i){int si;while(a[i1].va[i].v) i;for(int js;ji;j){xfind(a[j].f),yfind(a[j].to);if(xy) continue; g[x].push_back({y,j});g[y].push_back({x,j});}for(int js;ji;j){xfind(a[j].f),yfind(a[j].to);if(xy||dfn[x]) continue;tarjan(x,0);}for(int js;ji;j){xfind(a[j].f),yfind(a[j].to);dfn[x]dfn[y]0;g[x].clear(),g[y].clear();unite(x,y);}num0;}int out0;for(int i1;im;i) if(ans[i]) out;printf(%d\n,out);return 0;
}
