//给一个无向图，其每个顶点都有权值，求去掉一条边，将这个图分为两部分//问这两部分的所有顶点和的绝对值的最小值//用tarjan缩点 ， 缩点后为一棵树//然后用树形dp求出其最小的绝对值// ans = min(ans , (int)(abs((double)(sum – 2*dp[v])))) ;//其中dp[u] 表示以u点为根节点的子树的学生数#include<cstdio>#include<cstring>#include<iostream>#include<cmath>#include<vector>using namespace std ;const int maxn = 10010 ;const int maxm = 20010 ;const int inf = 0x7fffffff ;struct Edge{ int v , u; int next ;}edge[maxm<<1];int head[maxn] , dfn[maxn] , low[maxn] , vis[maxm<<1];int stack[maxn] , isstack[maxn] ,value[maxn] ,dp[maxn];int nedge , top , num , step ,sum;int n , m ;int belong[maxn] , stu[maxn];void addedge(int u , int v){ edge[nedge].v = v ; edge[nedge].next = head[u] ; head[u] = nedge++ ;}vector<int> vec[maxn] ;void init(){ memset(vis , 0 ,sizeof(vis)) ; memset(dfn , 0 ,sizeof(dfn)) ; memset(low , 0 , sizeof(low)) ; memset(isstack , 0 , sizeof(isstack)) ; memset(value , 0 , sizeof(value)); memset(head ,-1 , sizeof(head)) ; memset(dp , 0 , sizeof(dp)) ; for(int i = 0 ;i <= n;i++) vec[i].clear() ; top = num = step = nedge = sum = 0 ;}void tarjan(int u){ isstack[u] = 1 ; stack[++top] = u ; dfn[u] = low[u] = ++step; for(int i = head[u];i != -1 ; i = edge[i].next) { if(vis[i])continue ; vis[i] = vis[i^1] = 1 ; int v = edge[i].v ; if(!dfn[v]) { tarjan(v) ; low[u] = min(low[u] , low[v]) ; } else if(isstack[v]) low[u] = min(low[u] , dfn[v]) ; } if(dfn[u] == low[u]) { num++ ; int v ; while(u!=v) { v = stack[top–] ; belong[v] = num ; isstack[v] = 0 ; value[num] += stu[v] ; } }}void build_tree(){ for(int i = 1;i <= n;i++) for(int j = head[i] ; j != -1 ;j = edge[j].next) { int u = belong[i] ; int v = belong[edge[j].v] ; if(u == v)continue ; vec[u].push_back(v); }}void dfs(const int u , int &ans){ vis[u] = 1; for(int i = 0;i < vec[u].size();i++) { int v = vec[u][i] ; if(vis[v])continue ; dfs(v , ans) ; ans = min(ans , (int)(abs((double)(sum – 2*dp[v])))) ; dp[u] += dp[v] ; } dp[u] += value[u];}int main(){ //freopen("in.txt" , "r" , stdin) ; while(~scanf("%d%d" , &n , &m)) { int a , b ; init() ; for(int i = 1;i <= n;i++) { scanf("%d" , &stu[i]) ; sum += stu[i] ; } for(int i = 1;i <= m;i++) { scanf("%d%d" , &a , &b) ; addedge(a+1 , b+1) ; addedge(b+1 , a+1) ; } int ans = inf ; tarjan(1) ; build_tree() ; if(num <= 1)puts("impossible") ; else { memset(vis , 0 , sizeof(vis)) ; dfs(1 , ans) ; printf("%d\n" , ans) ; } } return 0 ;}
，你写PPT时，阿拉斯加的鳕鱼正跃出水面，
