弱联通
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#define inf 0x3f3f3f3f
#define N 10005
#define M 40005
typedef long long LL;
using namespace std;
stack<int>st;
int value[N];
struct Node{
int to,next;
}edge[M];
int tol,head[N];
struct rNode{
int to,next;
}redge[M];
int rtol,rhead[N];
void addedge(int u,int v){
edge[tol].to=v; edge[tol].next=head[u]; head[u]=tol++;
}
void raddedge(int u,int v){
redge[rtol].to=v; redge[rtol].next=rhead[u]; rhead[u]=rtol++;
}
int Belong[N],val[N],visit[N],Low[N],Dfn[N],cnt,scc,Ans,Sum; void Tarjan(int x,int father){
int i,j,flag=0;
Low[x]=Dfn[x]=cnt++;
visit[x]=1;
st.push(x);
for(i=head[x];i!=-1;i=edge[i].next){
int y=edge[i].to;
if(y==father && !flag) { flag=1; continue; }
if(!visit[y]) Tarjan(y,x);
Low[x]=min(Low[x],Low[y]);
}
if(Dfn[x]==Low[x]){
scc++; int v;
do{
v=st.top();
st.pop();
Belong[v]=scc;
val[scc]+=value[v];
}while(v!=x);
}
}
int Min(int a,int b){
if(a>b) return b;
return a;
}
int dfs(int x,int father){
int i,j;
int sum=val[x];
for(i=rhead[x];i!=-1;i=redge[i].next){
int y=redge[i].to;
if(y==father) continue;
sum+=dfs(y,x);
}
Ans=Min(Ans,abs(Sum-sum*2));
return sum;
}
int main(){
int n,m;
int i,j,k;
while(~scanf("%d %d",&n,&m)){
Sum=0;
tol=rtol=cnt=scc=0;
memset(head,-1,sizeof(head));
memset(rhead,-1,sizeof(rhead));
memset(visit,0,sizeof(visit));
memset(val,0,sizeof(val));
for(i=0;i<n;i++){
scanf("%d",&value[i]); Sum+=value[i];
}
for(i=0;i<m;i++){
int a,b; scanf("%d %d",&a,&b);
addedge(a,b); addedge(b,a);
}
Tarjan(0,0);
//for(i=0;i<n;i++) printf("%d %d\n",i,Belong[i]);
if(scc==1) {
printf("impossible\n"); continue;
}
for(i=0;i<n;i++)
for(j=head[i];j!=-1;j=edge[j].next){
int t1=Belong[i]; int t2=Belong[edge[j].to];
if(t1!=t2) raddedge(t1,t2);
}
Ans=inf;
dfs(1,0);
printf("%d\n",Ans);
}
return 0;
}
/*
【题意】
一个无向连通图 每个点有个值 求断开一条边使得形成两个联通图
并使两边的 点和之差 最小 【做法】
弱联通缩点 之后dfs即可 【思考】
第一写弱联通 学到了 */