题干：
小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⩽n<m⩽2∗105,1⩽边权⩽1062⩽n<m⩽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代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=200050;
int root,sum=1,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 w<A.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].v=v;
e[tot].id=id;
e[tot].next=first[u];
first[u]=tot++;
}
void tarjin(int u,int last){
dfn[u]=low[u]=sum++;
for(int i=first[u];~i;i=e[i].next){
int v=e[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);
tot=0;
memset(first,-1,sizeof(first));
for(i=1;i<=n;++i)f[i]=i;
for(i=0;i<m;++i){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
}
sort(E,E+m);
for(i=0;i<m;++i){
j=i;
while(j+1<m&&E[j+1].w==E[i].w)j++;
tot=0;
for(int k=i;k<=j;++k){
int fu=getf(E[k].u),fv=getf(E[k].v);
if(fu!=fv){
add(fu,fv,k);
add(fv,fu,k);
}
}
for(int k=i;k<=j;++k){
int fu=getf(E[k].u),fv=getf(E[k].v);
if(fu==fv || dfn[fu]) continue;
tarjin(fu,-1);
}
for(int k=i;k<=j;++k){
int fu=getf(E[k].u),fv=getf(E[k].v);
if(fu==fv)continue;
first[fu]=first[fv]=-1;
dfn[fu]=dfn[fv]=0;
f[fu]=fv;
}
i=j;
}
int h=0;
for(i=0;i<m;++i)h+=ans[i];
cout<<h<<endl;
return 0;
} AC代码2：
#include<bits/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 c<p.c;}
}e[maxm];
int n,m;
inline void init()
{
int p;
scanf("%d%d",&n,&m);scanf("%d",&p);
for(int i=1;i<=m;i++) e[i].read(i);
sort(e+1,e+m+1);
}
int head[maxn],nxt[maxm<<1],ver[maxm<<1],id[maxm<<1],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 i=head[x];i;i=nxt[i])
{
int y=ver[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 i=1;i<=n;i++) fa[i]=i;
int Nowedge=1;
while(Nowedge<=m)
{
int L=Nowedge,R=Nowedge;
while(R+1<=m&&e[R].c==e[R+1].c) R++;
Nowedge=R+1;cnt=0;tot=1;
for(int i=L;i<=R;i++)
{
int a=find(e[i].a),b=find(e[i].b);
head[a]=0;head[b]=0;dfn[a]=dfn[b]=low[a]=low[b]=0;
}
for(int i=L;i<=R;i++)
{
int a=find(e[i].a),b=find(e[i].b);
if(a==b)
{
ans[e[i].id]=-1;
continue;
}
ans[e[i].id]=233;
addedge(a,b,e[i].id);
}
for(int i=L;i<=R;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 i=L;i<=R;i++) fa[find(e[i].a)]=find(e[i].b);
}
int ttl = 0;
for(int i=1;i<=m;i++)
{
if(ans[i]==666) ttl++;
}
cout<<ttl<<endl;
return 0;
} AC代码3：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct edge{int f,to,v;}a[N];
struct node{int to,id;};
bool cmp(edge a,edge b){return a.v<b.v;}
int fa[N];vector<node>g[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){x=find(x),y=find(y),fa[x]=y;}
void tarjan(int x,int fa){
dfn[x]=low[x]=++num;
for(auto it:g[x]){
int u=it.to,id=it.id;
if(id==fa) 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 i=1;i<=m;i++) scanf("%d%d%d",&a[i].f,&a[i].to,&a[i].v);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int s=i;while(a[i+1].v==a[i].v) i++;
for(int j=s;j<=i;j++){
x=find(a[j].f),y=find(a[j].to);
if(x==y) continue;
g[x].push_back({y,j});
g[y].push_back({x,j});
}
for(int j=s;j<=i;j++){
x=find(a[j].f),y=find(a[j].to);
if(x==y||dfn[x]) continue;
tarjan(x,0);
}
for(int j=s;j<=i;j++){
x=find(a[j].f),y=find(a[j].to);
dfn[x]=dfn[y]=0;
g[x].clear(),g[y].clear();
unite(x,y);
}
num=0;
}
int out=0;for(int i=1;i<=m;i++) if(ans[i]) out++;
printf("%d\n",out);
return 0;
}
京公网安备 11010502036488号