pku 3694 Network

来源:转载

哎,写了差不多两天了,终于A了。。双联通分量+并查集。。

题目大意:给一个连通的无向图,问每加进来一条边,图中还有多少桥!

思路:刚开始想都没想,直接就写,每加进来一条边然后进行缩点,写到每加一条边然后重新建图的时候打住了,每加一条边要进行缩点,还要重新建图,太麻烦了,,

搞了很久还是写出来了,交上去OLE了,搜了一下解题报告, 人家说这种方法会超时,然后果断不写了。。

又看了一下discuss里面有人介绍到LCA最近公共祖先,又花了一上午时间把这个学学,之后再来做这道题,,发现方法不实用,我学的那个需要离线处理,

也就是先把数据输入进去完,对于这道题,每加一条边都要进行缩点,那种离线方法根本无法解。。

又重新看了下解题报告,里面说到每加进来一条边,都用暴力的方法求解Lca,然后判断从该点到Lca的 这个路径上的边是否标记过,如果没标记过 就num++,

然后把该边标记。。num表示这次缩点所减少的桥。。count-num表示当前剩下的桥。。

在重新改了几遍之后终于AC啦。。—=—。。。

贴一下我丑陋的代码吧:

View Code
 1 # include<stdio.h>
2 # include<string.h>
3 # define N 100005
4 # define M 200005
5 # include<stack>
6 using namespace std;
7 struct node{
8 int from,to,next;
9 }edge[2*M],edge1[2*M];
10 int head[N],tol,cnt,Q,Belong[N],tol1,head1[N],father[N],count,count1,n,m,dfn[N],low[N],visit1[N];
11 bool visit[N];
12 stack<int>S;
13 void add(int a,int b)
14 {
15 edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;
16 }
17 void add1(int a,int b)
18 {
19 edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
20 }
21 int min(int a,int b)
22 {
23 return a<b?a:b;
24 }
25 void tarjan(int u,int fa)
26 {
27 int j,v,flag;
28 dfn[u]=low[u]=cnt++;
29 S.push(u);
30 visit[u]=1;
31 flag=0;
32 for(j=head[u];j!=-1;j=edge[j].next)
33 {
34 v=edge[j].to;
35 if(v==fa && !flag) {flag=1;continue;}//重边!!!
36 if(!visit[v]) tarjan(v,u);
37 low[u]=min(low[u],low[v]);
38 }
39 if(dfn[u]==low[u])
40 {
41 count++;
42 do{
43 v=S.top();
44 S.pop();
45 Belong[v]=count;
46 }while(v!=u);
47 }
48 }
49 void dfs(int u,int fa)
50 {
51 int j,v;
52 father[u]=fa;
53 for(j=head1[u];j!=-1;j=edge1[j].next)
54 {
55 v=edge1[j].to;
56 if(v==fa) continue;
57 dfs(v,u);
58 }
59 }
60 //建树,为了用他们的father
61 int Lca(int a,int b,int c)
62 {
63 int num,ans,a1,b1;
64 visit1[a]=visit1[b]=c;
65 if(a==b) return 0;
66 a1=a;
67 b1=b;
68 while(1)
69 {
70 if(father[a1]!=a1)
71 {
72 a1=father[a1];
73 if(visit1[a1]==c) {ans=a1;break;}
74 visit1[a1]=c;
75 }
76 if(father[b1]!=b1)
77 {
78 b1=father[b1];
79 if(visit1[b1]==c) {ans=b1;break;}
80 visit1[b1]=c;
81 }
82 }
83 //找最近公共祖先
84 num=0;
85 while(a!=ans)
86 {
87 if(visit[a]==0) {visit[a]=1;num++;}
88 a=father[a];
89 }
90 while(b!=ans)
91 {
92 if(visit[b]==0) {visit[b]=1;num++;}
93 b=father[b];
94 }
95 return num;
96 }
97 int main()
98 {
99 int i,ncase=0,a,b,ans;
100 while(scanf("%d%d",&n,&m)!=EOF)
101 {
102 if(!n && !m) break;
103 ncase++;
104 tol=0;
105 memset(head,-1,sizeof(head));
106 for(i=1;i<=m;i++)
107 {
108 scanf("%d%d",&a,&b);
109 add(a,b);
110 add(b,a);
111 }
112 count=0;
113 cnt=0;
114 memset(visit,0,sizeof(visit));
115 tarjan(1,0);
116 tol1=0;
117 memset(head1,-1,sizeof(head1));
118 for(i=0;i<tol;i++)
119 {
120 a=edge[i].from;
121 b=edge[i].to;
122 if(Belong[a]!=Belong[b]) add1(Belong[a],Belong[b]);
123 }
124 //缩点之后重新建图
125 dfs(1,1);
126 count--;
127 printf("Case %d:/n",ncase);
128 scanf("%d",&Q);
129 memset(visit1,0,sizeof(visit1));
130 memset(visit,0,sizeof(visit));///标记边
131 for(i=1;i<=Q;i++)
132 {
133 scanf("%d%d",&a,&b);
134 a=Belong[a];
135 b=Belong[b];
136 ans=Lca(a,b,i);
137 count-=ans;
138 printf("%d/n",count);
139 }
140 printf("/n");
141 }
142 return 0;
143 }


分享给朋友:
您可能感兴趣的文章:
随机阅读: