题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4587
题目给了12000ms,对于tarjan这种O(|V|+|E|)复杂度的算法来说,暴力是能狗住的。可以对每个点进行枚举,然后对剩余的网络进行tarjan,对割点所能造成的最大的连通分量进行查询,也就是如下的方程。ans=max{cut[i]}+cnt 其中cnt删除第一个结点之后剩下的网络在初始时刻的连通分量的数量,也就是对每一个第一结点tarjan进行深搜的次数。另外,这次的tarjan中的cut数组存储的不再是这个点是否是割点,而是这个点“成为割点的次数”,也就是说,对于一个非根节点u来说,他有k个分支只能通过u来连接到u的祖先,所以u被删除之后就会多出来k个连通分量,这个cut的更新是在搜索完一个分支之后退回到u时更新的。对于根节点来说,由于他没有父结点,原先他所在的连通分量的分量数量为1,现在把它割掉,还剩k个子树的连通分量,也就是根节点使得连通分量的数量增加了k-1,这是不同于非根节点的。
代码如下:(还未解决,WA代码,先暂存着)
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x3f3f3f3f 20 const int maxn=5005; 21 const int maxm=10010; 22 int n,m,t; 23 int head[maxn],nxt[maxn],cut[maxn],dfn[maxn],low[maxn]; 24 struct node{ 25 int u,v; 26 }p[maxm]; 27 int e; 28 int first; 29 int id; 30 void addedge(int u,int v) 31 { 32 p[e].u=u; 33 p[e].v=v; 34 nxt[e]=head[u]; 35 head[u]=e++; 36 } 37 void tarjan(int u,int fa) 38 { 39 dfn[u]=low[u]=++id; 40 int child=0; 41 for(int i=head[u];~i;i=nxt[i]) 42 { 43 int v=p[i].v; 44 if(v==first||v==fa)continue;//假定了这个网络中没有first结点 45 if(!dfn[v]) 46 { 47 child++; 48 tarjan(v,u); 49 low[u]=min(low[u],low[v]); 50 if(low[v]>=dfn[u]&&u!=fa)cut[u]++;//非根结点成为割点,可割的连通分量的数量增加 51 if(u==fa&&child>=2)cut[u]++;//根节点,至少有两个子树 52 } 53 else if(dfn[v]<dfn[u]&&v!=fa) 54 { 55 low[u]=min(low[u],dfn[v]); 56 } 57 } 58 if(u==fa&&child>=1)cut[u]=child-1; 59 //更新根节点的cut值的唯一方法是通过子树的数量-1 60 //注意此时如果根节点的child值是1的话更新之后是0,所以不能加child>1的条件 61 } 62 int main() 63 { 64 //freopen("input.txt","r",stdin); 65 //freopen("output.txt","w",stdout); 66 std::ios::sync_with_stdio(false); 67 while(scanf("%d%d",&n,&m)!=EOF) 68 { 69 int x,y; 70 f(i,0,maxn-1)head[i]=-1,nxt[i]=-1; 71 e=0; 72 f(i,1,m) 73 { 74 scanf("%d%d",&x,&y); 75 addedge(x,y); 76 addedge(y,x); 77 } 78 int curnum; 79 int ans=0; 80 f(i,0,n-1)//枚举每一个点,再用tarjan对割点进行查找,找到割点增加连通分量最多的点。 81 { 82 f(i,0,n-1)dfn[i]=0,cut[i]=0;//要进行n次对这个网络的tarjan,每次都要清零 83 first=i; 84 curnum=0; 85 id=0; 86 f(j,0,n-1) 87 { 88 if(i==j)continue; 89 if(!dfn[j]) 90 { 91 tarjan(j,j); 92 curnum++; 93 } 94 } 95 f(j,0,n-1) 96 { 97 if(j!=i) ans=max(ans,curnum+cut[j]); 98 } 99 } 100 pf("%d\n",ans); 101 } 102 return 0; 103 }