hdu 2242 无向图/求用桥一分为二后使俩个bcc点权值和之差最小并输出 /缩点+2次新图dfs

题意如标题所述，

先无向图缩点，统计出每个bcc权，建新图，然后一遍dfs生成树，标记出每个点（新图）以及其子孙的权值之和。这样之后就可以dfs2来枚举边（原图的桥）,更新最小即可。

调试了半天！原来是建老图时候链式前向星和新图的vector<vector< int>>俩种存图搞乱了！！！不可原谅！哎！愚蠢！愚不可及！提交后1A。

后来百度之后，发现说是用树形dp，看了代码解法，竟然和我的是一样的算法。。原来这种算法可以叫树形dp。。。的确有点dp味道。。不过感觉不太浓。。

以后多个图，多种储存方式要分清！e[i][j]!!!e[u][i]\e[j][1]。。。

#include<iostream>

#include<cstdio>

#include<stack>

#include<vector>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxv=10010,maxe=50000;

int head[maxv];int nume=0;int e[maxe][2];

void inline adde(int i,int j)

{

    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume++;

    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume++;

}

int dfn[maxv];int low[maxv];int vis[maxv];int bcc[maxv];int ins[maxv];stack<int>sta;

int times=0; int numb=0; int vise[maxe];

int wi[maxv]; int sumwi[maxv];

void tarjan(int u)

{

     dfn[u]=low[u]=times++;

     ins[u]=1;

     sta.push(u);

     for(int i=head[u];i!=-1;i=e[i][1])

     {

         if(vise[i])continue;

         int v=e[i][0];

         if(!vis[v])

         {

             vis[v]=1;

             vise[i]=vise[i^1]=1;

             tarjan(v);

             if(low[v]<low[u])low[u]=low[v];

         }

         else if(ins[v]&&dfn[v]<low[u])

            low[u]=dfn[v];

     }

     if(low[u]==dfn[u])

     {

         numb++;

         int cur;

         do{

             cur=sta.top();

             sta.pop();

             ins[cur]=0;

             bcc[cur]=numb;

             sumwi[numb]+=wi[cur];

         }while(cur!=u);

     }

}

vector<vector<int> >e2(maxv+1);

int n,m; int mindis=inf;

int getabs(int x)

{

    return x<0?-x:x;

}

void init()

{

    numb=times=nume=0;mindis=inf;

    memset(vise,0,sizeof(vise));

    for(int i=0;i<maxv;i++)

      {

         sumwi[i]=wi[i]=bcc[i]=ins[i]=dfn[i]=low[i]=vis[i]=0;

         e2[i].clear(); head[i]=-1;

      }

}

int dfs(int u)             //获得sumwi【i】:子孙包括自己的权值和

{

    for(int i=0;i<e2[u].size();i++)

    {

        int v=e2[u][i];

        if(!vis[v])

        {

            vis[v]=1;

            sumwi[u]+=dfs(v);

        }

    }

    return sumwi[u];

}

void dfs2(int u)

{

   for(int i=0;i<e2[u].size();i++)

    {

        int v=e2[u][i];

        if(!vis[v])

        {

            if(getabs(sumwi[1]-sumwi[v]-sumwi[v])<mindis)

            {

                mindis=getabs(sumwi[1]-sumwi[v]-sumwi[v]);

            }

            vis[v]=1;

            dfs2(v);

        }

    }

}

void solve()

{

    vis[0]=1;

    tarjan(0);

   if(numb==1)

   {

       printf("impossible\n");

       return ;

   }

   memset(vise,0,sizeof(vise));

   for(int i=0;i<n;i++)

     for(int j=head[i];j!=-1;j=e[j][1])

        if(bcc[i]!=bcc[e[j][0]]&&vise[j]==0)

            {

                e2[bcc[i]].push_back(bcc[e[j][0]]);

                e2[bcc[e[j][0]]].push_back(bcc[i]);

                vise[j]=vise[j^1]=1;

            }

    memset(vis,0,sizeof(vis));

    vis[1]=1;

    dfs(1);

    memset(vis,0,sizeof(vis));

    vis[1]=1;

    dfs2(1);

   printf("%d\n",mindis);

}

void readin()

{

    for(int i=0;i<n;i++)

        scanf("%d",&wi[i]);

    int aa,bb;

    for(int i=0;i<m;i++)

    {

        scanf("%d%d",&aa,&bb);

        adde(aa,bb);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

        readin();

        solve();

    }

    return 0;

}

巴特西

hdu 2242 无向图/求用桥一分为二后使俩个bcc点权值和之差最小并输出 /缩点+2次新图dfs

最新文章

热门文章