HDU 2242 连通分量缩点+树形dp

题目大意是：

所有点在一个连通图上，希望去掉一条边得到两个连通图，且两个图上所有点的权值的差最小，如果没有割边，则输出impossible

这道题需要先利用tarjan算法将在同一连通分量中的点缩成一个点后，重新构建一幅图，然后利用新建的图进行树形dp解决问题

这道题目需要注意的是可能存在重边，那么子节点回到父节点有两条边及以上的话，就需要对子节点经过父节点的边进行low值更新

tarjan算法学习的网站个人感觉还不错https://www.byvoid.com/blog/scc-tarjan/

  1 /*
  2 找割边是否存在
  3 */
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <iostream>
  7 #include <stack>
  8 using namespace std;
  9 
 10 typedef long long ll;
 11 const int N = 10005;
 12 const int INF = 200000000;
 13 
 14 int first[N] , k , k_scc , val[N] , val_scc[N] , sum[N] , all ;
 15 int scc[N] , num_of_scc , dfs_clock , dfn[N] , low[N];
 16 stack<int> s;
 17 
 18 struct Edge{
 19     int x , y , next ;
 20     bool flag;
 21 }e[N<<2] , e_scc[N<<2];
 22 
 23 int my_abs(int x)
 24 {
 25     return x>=0?x:-x;
 26 }
 27 
 28 void add_edge(int x , int y)
 29 {
 30     e[k].x = x , e[k].y = y , e[k].next = first[x];
 31     first[x] = k++;
 32 }
 33 
 34 void add_edge_scc(int x , int y)
 35 {
 36     e_scc[k_scc].x = x , e_scc[k_scc].y = y , e_scc[k_scc].next = first[x] , e_scc[k_scc].flag = false;
 37     first[x] = k_scc++;
 38 }
 39 
 40 void tarjan(int u , int fa)
 41 {
 42     dfn[u] = low[u] = ++dfs_clock;
 43     s.push(u);
 44     int flag = 1; //用来解决重边情况
 45     for(int i=first[u] ; i!=-1 ; i=e[i].next){
 46         int v = e[i].y;
 47         /*
 48         因为第一次遇到父节点的边，表示是一开始下来的边，这个是不允许访问的，
 49         但是如果遇到2次及以上，说明u v之间不止一条边，访问到第二次之后的边是允许
 50         low[u]通过这个重边得到dfn[v]比较下的较小值进行更新
 51         */
 52         if(v == fa && flag){
 53             flag = 0;
 54             continue;
 55         }
 56         if(!dfn[v]){
 57             tarjan(v,u);
 58             low[u] = min(low[u] , low[v]);
 59         }
 60         else if(!scc[v])
 61             low[u] = min(low[u] , dfn[v]);
 62     }
 63     if(low[u] == dfn[u]){
 64         num_of_scc++;
 65         while(true){
 66             int x = s.top();
 67             s.pop();
 68             scc[x] = num_of_scc;
 69             val_scc[num_of_scc] += val[x];//得到新构建图上的点的权值
 70             if(x == u) break;
 71         }
 72     }
 73 }
 74 
 75 void dfs(int u , int fa)
 76 {
 77     sum[u] = val_scc[u];
 78     for(int i=first[u] ; i!=-1 ; i=e_scc[i].next){
 79         int v = e_scc[i].y;
 80         if(v == fa) continue;
 81         e_scc[i].flag = true;
 82         dfs(v , u);
 83         sum[u]+=sum[v];
 84     }
 85 }
 86 
 87 int main()
 88 {
 89   //  freopen("a.in" , "r" , stdin);
 90     int n , m , x , y;
 91     while(scanf("%d%d" , &n , &m) == 2){
 92         memset(first , -1 , sizeof(first));
 93         k=0 , all = 0;
 94         for(int i=0 ; i<n ; i++)
 95         {
 96             scanf("%d" , val+i);
 97             all += val[i];
 98         }
 99 
100         for(int i=0 ; i<m ; i++){
101             scanf("%d%d" , &x , &y);
102             add_edge(x , y);
103             add_edge(y , x);
104         }
105 
106         //强连通分量缩点
107         dfs_clock = 0 , num_of_scc = 0;
108         memset(dfn , 0 ,sizeof(dfn));
109         memset(scc , 0 , sizeof(scc));
110         memset(val_scc , 0 , sizeof(val_scc));
111         tarjan(0 , -1);
112 
113         if(num_of_scc == 1){
114             puts("impossible");
115             continue;
116         }
117 
118         //重新构建一个以连通分量缩点后的树形图
119         memset(first , -1 , sizeof(first));
120         k_scc = 0;
121         for(int i=0 ; i<k ; i++){
122             if(scc[e[i].x] == scc[e[i].y]) continue;
123             add_edge_scc(scc[e[i].x] , scc[e[i].y]);
124         }
125         dfs(1 , -1);
126 
127         int minn = INF;
128         for(int i=0 ; i<k_scc ; i++){
129             if(!e_scc[i].flag) continue;
130             minn = min(minn , my_abs(all - sum[e_scc[i].y] - sum[e_scc[i].y]) );
131         }
132         printf("%d
" , minn);
133     }
134     return 0;
135 }