考研路茫茫——空调教室

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<vector>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 5e4+10, M = 4e4+10, mod = 1e9+7, inf = 2e9;int all;int vis[N];int n,m,a[N],vv[N],uu[N];int head[M],belong[N],inq[N];int dfn[N],low[N],scc,siz[N],tot,ans,top,t,hav[N],q[N];vector<int > G[N];void init() {        scc = 0;        all = 0;        tot = 0;        top = 0;        t = 0;        memset(head,-1,sizeof(head));        memset(dfn,0,sizeof(dfn));        memset(hav,0,sizeof(hav));}struct node{int to,next,id;}e[N * 4];void dfs(int u,int fa) {        dfn[u]=low[u]=++tot;        q[++top] = u;        inq[u] = 1;        for(int i = head[u]; i != -1; i = e[i].next) {            int to = e[i].to;            if(e[i].id) continue;            e[i].id = e[i^1].id = 1;            if(!dfn[to]) {                dfs(to,u);                low[u] = min(low[u],low[to]);            } else if(inq[to]) low[u] = min(low[u],dfn[to]);        }        if(low[u] == dfn[u]) {            scc++;            do{                inq[q[top]] = 0;                belong[q[top]]=scc;                hav[scc]+=a[q[top]];            }while(u!=q[top--]);        }}void add(int u,int v) {        e[t].to=v;        e[t].next=head[u];        e[t].id = 0;        head[u]=t++;}void Tarjan() {        for(int i = 1; i <= n; ++i) {            if(!dfn[i])            {                dfs(i,-1);            }        }}void dfs2(int u,int fa) {        siz[u] = hav[u];        for(int i = 0; i < G[u].size(); ++i) {            int to = G[u][i];            if(to == fa) continue;            dfs2(to,u);            siz[u] += siz[to];            ans = min(ans,abs(all - siz[to] - siz[to]));        }}int main() {        while(~scanf("%d%d",&n,&m)) {            init();            for(int i = 1; i <= n; ++i) scanf("%d",&a[i]),all += a[i];            for(int i = 1; i <= m; ++i) {                int u,v;                scanf("%d%d",&u,&v);                u++,v++;                add(u,v),add(v,u);                uu[i] = u;                vv[i] = v;            }            Tarjan();            //cout<<scc<<endl;           // return 0;            for(int i = 0; i <= scc; ++i) G[i].clear();            for(int i = 1; i <= m; ++i) {                int u = belong[uu[i]];                int v = belong[vv[i]];                if(u == v) continue;                G[u].push_back(v);                G[v].push_back(u);            }            ans = inf;            dfs2(1,0);            if(ans == inf) puts("impossible");            else            printf("%d\n",ans);        }        return 0;}