题目大意：给定一个连通无向图，每个结点有一个值，现要断开图中某条边，使得原图变成两个连通子图，且要使两个子图的值的差最小。输出最小差，若无法完成，则输出"impossible”

分析：要使断开某条边后，原图变成两个连通支，则断开的边一定是桥。对图进行DFS时，得到一颗树，图中有的而树中没有的边叫回边，回边一定不是桥。由此想到可用dfs将图转化为树来做，但树中的边不一定是原图中的桥，问题关键在于桥的判断。此题还需要注意的是可能有重边。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #define N 10001  6 #define M 40001  7 #define INF 0x7fffffff  8 #define MAX(a,b) ((a)>(b)?(a):(b))  9 #define MIN(a,b) ((a)<(b)?(a):(b)) 10 using namespace std; 11 vector
          
            dep[N]; 12 int u[M],v[M],cnt[M],next[M],first[N],n,m; 13 int num[N],sum[N]; 14 int p[N],d[N],dfn[N],low[N],dmax,id; 15 char vis[N]; 16 void dfs(int a,int fa) 17 { 18   int e,b; 19   d[a]=(fa==-1?0:d[fa]+1); 20   dmax=MAX(dmax,d[a]); 21   dep[d[a]].push_back(a); 22   for(e=first[a];e>=0;e=next[e]) 23   { 24     b=v[e]; 25     if(b==fa) continue; 26     if(vis[b])  low[a]=MIN(low[a],dfn[b]); 27     else 28     { 29       vis[b]=1; 30       dfn[b]=low[b]=++id; 31       dfs(b,p[b]=a); 32       low[a]=MIN(low[a],low[b]); 33     } 34   } 35 } 36 void dp() 37 { 38   int e,b,i,j; 39   memset(sum,0,sizeof(sum)); 40   for(i=dmax;i>=0;i--) 41   { 42     for(j=0;j
           
            =0;e=next[e]) 61 { 62 if(v[e]==b) 63 { 64 cnt[e]++; 65 return 1; 66 } 67 } 68 return 0; 69 } 70 int main() 71 { 72 int i,e,a,b,ans; 73 while(~scanf("%d%d",&n,&m)) 74 { 75 for(i=0;i
            
             1) continue;102 a=u[2*e],b=v[2*e];103 if(p[a]==b&&low[a]>dfn[b]) ans=MIN(ans,abs(2*sum[a]-sum[0]));104 else if(p[b]==a&&low[b]>dfn[a]) ans=MIN(ans,abs(2*sum[b]-sum[0]));105 }106 if(ans==INF) puts("impossible");107 else printf("%d\n",ans);108 }109 return 0;110 }