[文章目录]
Description
他去找市长帮他修路，使得每两个糖果店之间至少有两条完全不同的路。可是市长经费有限，于是让桐桐找出哪些路被塞住后会使某些糖果店与糖果店间无法到达及最少的修路条数。 注：1-> 3-> 2 和 1-> 3-> 4-> 2 为不完全不同的路，即不符合题意的路。 1-> 3-> 4-> 2 和 1-> 5-> 2 为完全不同的路，即符合题意的路。
（n< =5000，m< =10000）
首先第一问就是求不在环上的边（割边）有多少个。第二问，显然缩点以后就是一棵树了，就是求如何加最少的边使树强连通。答案是叶子结点的数量/2。（把叶子结点lca尽量远的点相连，两两加边形成环）。找的话当然是只能到达一个强连通分量的强连通分量啦！
然后无向图的tarjan怎么办呢?——可以每次搜索时记录自己的fa是谁，然后搜索时跳过就好了。
至于求割边，有两种方法，第一种是将强连通分量缩点后的树上的边数求出来
for(int i=1;i<=ans;i++)
{
memset(v,0,sizeof(v));
flag=0;
for(int j=h1[i];j;j=nxt1[j])
{
for(int k=h[to1[j]];k;k=nxt[k])
if(belong[to[k]]!=belong[to1[j]])
v[belong[to[k]]]=1;
}
for(int i=1;i<=ans;i++)
if(v[i])
flag++;
fna+=flag;
}
fna/=2;还有一种就是：dfs搜索树子树结点没有一个能够到达根的父亲及父亲以上结点。就是说这颗子树被完全封死了，这条边就是桥。如果(a,b)有边，并且low[b]>deep[a]，那么（a，b）就是桥。也就是tarjan之后b点所能到追溯到的结点的深度编号要比a的深度要大，说明b点不能到达a的父亲及以上结点。
for(int i=1;i<=n;i++)
{
for(int j=h[i];j;j=nxt[j])
{
if(low[to[j]]>deep[i])
fna++;
}
}
变清真了有木有
所以此题我用的是第一种方法，因为这样还能顺便带出第2题的解233。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 5100
#define M 21000
using namespace std;
int n,m,flag,sum,t,a,b,fna;
int h[N],to[M],nxt[M],cnt,belong[N];
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=h[x];
h[x]=cnt;
}
int h1[N],to1[M],nxt1[M],cnt1;
void add1(int x,int y)
{
to1[++cnt1]=y;
nxt1[cnt1]=h1[x];
h1[x]=cnt1;
}
int deep[N],low[N],ans,z[N],top,tot;
int rd[N],cd[N];
bool inz[N];
void tarjan(int x,int pre)
{
deep[x]=low[x]=++tot;
z[++top]=x;
inz[x]=1;
for(int i=h[x];i;i=nxt[i])
if(to[i]!=pre)
{
if(!deep[to[i]])
{
tarjan(to[i],x);
if(low[to[i]]<low[x])
low[x]=low[to[i]];
}
else if(inz[to[i]]&&deep[to[i]]<low[x])
low[x]=deep[to[i]];
}
if(deep[x]==low[x])
{
ans++;
do
{
t=z[top--];
inz[t]=0;
belong[t]=ans;
add1(ans,t);
}while(t!=x);
}
return ;
}
bool v[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++)
{
if(!deep[i])
{
tarjan(i,0);
}
}
/*for(int i=1;i<=ans;i++)
{
printf("%d :",i);
for(int j=h1[i];j;j=nxt1[j])
printf("%d ",to1[j]);
puts("");
}*/
/*for(int i=1;i<=n;i++)
{
for(int j=h[i];j;j=nxt[j])
{
if(low[to[j]]>deep[i])
fna++;
}
}*/
/*for(int i=1;i<=n;i++)
printf("%d ",belong[i]);*/
for(int i=1;i<=ans;i++)
{
memset(v,0,sizeof(v));
flag=0;
for(int j=h1[i];j;j=nxt1[j])
{
for(int k=h[to1[j]];k;k=nxt[k])
if(belong[to[k]]!=belong[to1[j]])
v[belong[to[k]]]=1;
}
for(int i=1;i<=ans;i++)
if(v[i])
flag++;
if(flag==1)
sum++;
fna+=flag;
/*for(int i=1;i<=ans;i++)
printf("%d ",v[i]);
puts("");*/
}
fna/=2;
if(sum&1)
sum=sum/2+1;
else
sum/=2;
printf("%d\n%d",fna,sum);
return 0;
}