题意如标题所述，
先无向图缩点，统计出每个bcc权，建新图，然后一遍dfs生成树，标记出每个点（新图）以及其子孙的权值之和。这样之后就可以dfs2来枚举边（原图的桥）,更新最小即可。
调试了半天！原来是建老图时候链式前向星和新图的vector<vector< int>>俩种存图搞乱了！！！不可原谅！哎！愚蠢！愚不可及！提交后1A。
后来百度之后，发现说是用树形dp，看了代码解法，竟然和我的是一样的算法。。原来这种算法可以叫树形dp。。。的确有点dp味道。。不过感觉不太浓。。
以后多个图，多种储存方式要分清！e[i][j]!!!e[u][i]\e[j][1]。。。
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxv=10010,maxe=50000;
int head[maxv];int nume=0;int e[maxe][2];
void inline adde(int i,int j)
{
e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++;
e[nume][0]=i;e[nume][1]=head[j];head[j]=nume++;
}
int dfn[maxv];int low[maxv];int vis[maxv];int bcc[maxv];int ins[maxv];stack<int>sta;
int times=0; int numb=0; int vise[maxe];
int wi[maxv]; int sumwi[maxv];
void tarjan(int u)
{
dfn[u]=low[u]=times++;
ins[u]=1;
sta.push(u);
for(int i=head[u];i!=-1;i=e[i][1])
{
if(vise[i])continue;
int v=e[i][0];
if(!vis[v])
{
vis[v]=1;
vise[i]=vise[i^1]=1;
tarjan(v);
if(low[v]<low[u])low[u]=low[v];
}
else if(ins[v]&&dfn[v]<low[u])
low[u]=dfn[v];
}
if(low[u]==dfn[u])
{
numb++;
int cur;
do{
cur=sta.top();
sta.pop();
ins[cur]=0;
bcc[cur]=numb;
sumwi[numb]+=wi[cur];
}while(cur!=u);
}
}
vector<vector<int> >e2(maxv+1);
int n,m; int mindis=inf;
int getabs(int x)
{
return x<0?-x:x;
}
void init()
{
numb=times=nume=0;mindis=inf;
memset(vise,0,sizeof(vise));
for(int i=0;i<maxv;i++)
{
sumwi[i]=wi[i]=bcc[i]=ins[i]=dfn[i]=low[i]=vis[i]=0;
e2[i].clear(); head[i]=-1;
}
}
int dfs(int u) //获得sumwi【i】:子孙包括自己的权值和
{
for(int i=0;i<e2[u].size();i++)
{
int v=e2[u][i];
if(!vis[v])
{
vis[v]=1;
sumwi[u]+=dfs(v);
}
}
return sumwi[u];
}
void dfs2(int u)
{
for(int i=0;i<e2[u].size();i++)
{
int v=e2[u][i];
if(!vis[v])
{
if(getabs(sumwi[1]-sumwi[v]-sumwi[v])<mindis)
{
mindis=getabs(sumwi[1]-sumwi[v]-sumwi[v]);
}
vis[v]=1;
dfs2(v);
}
}
}
void solve()
{
vis[0]=1;
tarjan(0);
if(numb==1)
{
printf("impossible\n");
return ;
}
memset(vise,0,sizeof(vise));
for(int i=0;i<n;i++)
for(int j=head[i];j!=-1;j=e[j][1])
if(bcc[i]!=bcc[e[j][0]]&&vise[j]==0)
{
e2[bcc[i]].push_back(bcc[e[j][0]]);
e2[bcc[e[j][0]]].push_back(bcc[i]);
vise[j]=vise[j^1]=1;
}
memset(vis,0,sizeof(vis));
vis[1]=1;
dfs(1);
memset(vis,0,sizeof(vis));
vis[1]=1;
dfs2(1);
printf("%d\n",mindis);
}
void readin()
{
for(int i=0;i<n;i++)
scanf("%d",&wi[i]);
int aa,bb;
for(int i=0;i<m;i++)
{
scanf("%d%d",&aa,&bb);
adde(aa,bb);
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
readin();
solve();
}
return 0;
}
hdu 2242 无向图/求用桥一分为二后使俩个bcc点权值和之差最小并输出 /缩点+2次新图dfs,布布扣,bubuko.com
hdu 2242 无向图/求用桥一分为二后使俩个bcc点权值和之差最小并输出 /缩点+2次新图dfs
原文：http://blog.csdn.net/u011498819/article/details/38686615