hdu 3061 hdu 3996 最大权闭合图最后一斩

hdu 3061 Battle :一看就是明显的最大权闭合图了，水提。。。。。。SB题也不说边数多少。。。。因为开始时候数组开小了，WA。。。。后来一气之下，开到100W，A了。。

hdu3996. gold mine。。看了一下，简单题，几乎裸，不敲了。。

#include<iostream>//Battle

#include<queue>

#include<cstdio>

#include<cstring>

#include<set>

#include<vector>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxv=1000,maxe=1000000;

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

void inline adde(int i,int j,int c)

{

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

    e[nume++][2]=c;

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

    e[nume++][2]=0;

}

int ss,tt,n,m;

int vis[maxv];int lev[maxv];

bool bfs()

{

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

      vis[i]=lev[i]=0;

    queue<int>q;

    q.push(ss);

    vis[ss]=1;

    while(!q.empty())

    {

        int cur=q.front();

        q.pop();

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

        {

            int v=e[i][0];

            if(!vis[v]&&e[i][2]>0)

            {

                lev[v]=lev[cur]+1;

                vis[v]=1;

                q.push(v);

            }

        }

    }

    return vis[tt];

}

int dfs(int u,int minf)

{

    if(u==tt||minf==0)return minf;

    int sumf=0,f;

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

    {

        int v=e[i][0];

        if(lev[v]==lev[u]+1&&e[i][2]>0)

        {

            f=dfs(v,minf<e[i][2]?minf:e[i][2]);

            e[i][2]-=f;e[i^1][2]+=f;

            sumf+=f;minf-=f;

        }

    }

    if(!sumf) lev[u]=-1;

    return sumf;

}

int dinic()

{

    int sum=0;

    while(bfs())sum+=dfs(ss,inf);

    return sum;

};

int cpy[maxv];int sumz=0;

void read_build()

{

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

    {

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

        if(cpy[i]<0)

         adde(i,tt,-cpy[i]);

        else

         {

             adde(ss,i,cpy[i]);

              sumz+=cpy[i];

         }

    }

    int aa,bb;

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

     {

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

        adde(aa,bb,inf);

     }

  /*  for(int i=1;i<=m+2;i++)

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

      {

           if(j%2==0)

          printf("%d->%d:%d\n",i,e[j][0],e[j][2]);

      }*/

}

void init()

{

    nume=0;sumz=0;

    ss=n+1;tt=ss+1;

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

      {

       head[i]=-1;

      }

}

int main()

{

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

     {

         init();

        read_build();

       int ans;

       ans=sumz-dinic();

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

    }

    return 0;

}

巴特西

hdu 3061 hdu 3996 最大权闭合图最后一斩

最新文章

热门文章

巴特西

hdu 3061 hdu 3996 最大权闭合图 最后一斩

最新文章

热门文章

hdu 3061 hdu 3996 最大权闭合图最后一斩