这题是双连通缩点，缩完点后原图会变成一棵树，这棵树的边就是割边，之后只要dfs一遍这颗树，取最小值即可，这题有个陷阱，就是有重边，显然如果有重边的话，这两个点可以构成双连通，我们只需标记一下是第几次走这条边即可，超过一次的话就是重边，要计算这条重边。

Run ID	Submit Time	Judge Status	Pro.ID	Exe.Time	Exe.Memory	Code Len.	Language	Author
5479734	2012-03-06 14:30:10	Accepted	2242	218MS	1716K	2450 B	G++	xym2010

#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n,m,pos,ans,cnt,res[10005],head[10005],col[10005],dfn[10005],low[10005],bch,ord,stack[10005],top,tr[10005],sum[10005];
vector< pair<int,int> >brige;
bool vd[10005];
struct edge
{int v,next;
}eg[40005];
void insert(int x,int y)
{eg[pos].v=y,eg[pos].next=head[x],head[x]=pos++;
}
void tarjan(int u,int f)
{dfn[u]=low[u]=ord++;vd[u]=true;stack[top++]=u;int flag=0;//标记重边for(int i=head[u];i>=0;i=eg[i].next){int v=eg[i].v;if(v==f&&!flag&&(flag=1,1))continue;if(!vd[v])tarjan(v,u),low[u]=min(low[u],low[v]);else if(col[v]==-1)low[u]=min(low[u],dfn[v]);if(dfn[u]<low[v])brige.push_back(make_pair(u,v));}if(low[u]==dfn[u]){while(stack[top-1]!=u)col[stack[--top]]=bch,sum[bch]+=res[stack[top]];top--,sum[bch]+=res[stack[top]],col[u]=bch++;}
}
void buildT()
{memset(tr,-1,sizeof(tr));for(int i=0;i<brige.size();i++){int u=brige[i].first,v=brige[i].second;eg[pos].v=col[v],eg[pos].next=tr[col[u]];tr[col[u]]=pos++;eg[pos].v=col[u],eg[pos].next=tr[col[v]];tr[col[v]]=pos++;}
}
int dfs(int u)
{int tem=sum[u];vd[u]=1;for(int i=tr[u];i>=0;i=eg[i].next)if(!vd[eg[i].v])tem+=dfs(eg[i].v);ans=min(ans,abs(cnt-2*tem));return tem;
}
int main()
{int x,y;while(~scanf("%d%d",&n,&m)){cnt=0;for(int i=0;i<n;i++)scanf("%d",&res[i]),cnt+=res[i];memset(head,-1,sizeof(head));pos=0;for(int i=0;i<m;i++){scanf("%d%d",&x,&y);insert(x,y),insert(y,x);}bch=ord=top=0;memset(col,-1,sizeof(col));memset(vd,0,sizeof(vd));memset(sum,0,sizeof(sum));brige.clear();tarjan(0,0);if(bch==1)puts("impossible");else{buildT();ans=1<<29;memset(vd,0,sizeof(vd));dfs(0);printf("%d\n",ans);}}return 0;
}