/**//* 题意:给出一些点,有值,给出一些边,然后求去掉一条边后将分成连通的两部分,且两部分的差值最小 先将双连通分量缩点,成为一棵树,树边即桥,然后再递归一下就行 注意,这里的重边当成两条路!!! 如 1-0 1-0 则他们属双连通
与poj 3140类似,不过那道简单点,给出的是树,就注意下__int64 还有,如果stack overflow的话,试试在代码最前面加 #pragma comment(linker, "/STACK:102400000,102400000") 还是有问题的话,那就是代码问题了 */ #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std;
const int MAXN=10010; const int INF=2000000000;
struct Node{ int v,next; }nodes[MAXN*2];
int G[MAXN],low[MAXN],level[MAXN]; int color[MAXN]; int sum[MAXN],A[MAXN]; int ans,N; int vi[MAXN]; vector<pair<int,int> >Bridge;//存桥,方便重新建图 int alloc,n,m,ID;
void add(int a,int b){ nodes[alloc].v=b;nodes[alloc].next=G[a]; G[a]=alloc++; }
void dfs(int u,int p,int dep){ vi[u]=1; level[u]=low[u]=dep; bool flag=true;//因为可能有重边v->u,但第一条不算有效的(属u->v),所以标记一下flag即可,很重要! for(int son=G[u];son!=-1;son=nodes[son].next){ int v=nodes[son].v; if(v==p&&flag){ flag=false; continue; } if(vi[v]==1)low[u]=min(low[u],level[v]); else if(vi[v]==0){ dfs(v,u,dep+1); low[u]=min(low[u],low[v]); if(low[v]>level[u]) Bridge.push_back(make_pair(u,v)); } } vi[u]=2; }
void setColor(int u,int p){ sum[color[u]]+=A[u]; for(int son=G[u];son!=-1;son=nodes[son].next){ int v=nodes[son].v; if(color[v])continue; if(low[v]>level[u])color[v]=++ID; else color[v]=color[u]; setColor(v,u); } }
int DP(int u,int p){ A[u]=sum[u]; for(int son=G[u];son!=-1;son=nodes[son].next){ int v=nodes[son].v; if(v==p)continue; int tmp=DP(v,u); A[u]+=tmp; ans=min(ans,abs(N-tmp*2)); } return A[u]; }
int main(){ int a,b,t=1; while(~scanf("%d%d",&n,&m)){ N=0; for(int i=0;i<n;i++){ scanf("%d",&A[i]); N+=A[i]; } alloc=0; memset(G,-1,sizeof(int)*n); for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); add(a,b);add(b,a); } Bridge.clear(); memset(vi,0,sizeof(int)*n); dfs(0,0,0);
memset(color,0,sizeof(int)*n); memset(sum+1,0,sizeof(int)*n); color[0]=ID=1; setColor(0,0); //build again memset(G+1,-1,sizeof(int)*ID); alloc=0; for(int i=0;i<Bridge.size();i++){ int u=Bridge[i].first,v=Bridge[i].second; //是add color[u],不是u add(color[u],color[v]);add(color[v],color[u]); } if(ID==1)puts("impossible");//只有一个点时就是impossible else { ans=INF; DP(1,1);//这里是1开始,前面是0开始 printf("%d\n",ans); } } return 0; }
|