hdu2448 / 费用流 / harbin赛区c题

题（自）目（己）错（英）综（语）复（太）杂（差），关系理了半小时+翻译才看明白，看明白之后，直接建图，费用流击杀。/简单题。

2A:有的地方，可用互通的要建双向边！

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<string>

using namespace std;

const int maxv=400;

const int maxe=400*400*2+800;

const int inf=0x3f3f3f3f;

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

int n,m,k,p;

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

{

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

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

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

    e[nume][2]=0;e[nume++][3]=-w;

}

int inq[maxv];int pre[maxv];int prv[maxv];

int d[maxv];

int froms[maxv];

bool spfa(int &sum,int &flow)

{

    int s=0,t=n+m+1;

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

          {

              inq[i]=0;

              d[i]=inf;

          }

    queue<int>q;

    q.push(s);

    inq[s]=1;

    d[s]=0;

    while(!q.empty())

    {

        int cur=q.front();

        q.pop();

        inq[cur]=0;

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

        {

            int v=e[i][0];

            if(e[i][2]>0&&d[cur]+e[i][3]<d[v])

            {

                d[v]=d[cur]+e[i][3];

                pre[v]=i;

                prv[v]=cur;

                if(!inq[v])

                {

                    q.push(v);

                    inq[v]=1;

                }

            }

        }

    }

    if(d[t]==inf)return 0;

    int cur=t;

    int minf=inf;

    while(cur!=s)

    {

        int fe=pre[cur];

        minf=e[fe][2]<minf?e[fe][2]:minf;

        cur=prv[cur];

    }

     cur=t;

    while(cur!=s)

    {

        e[pre[cur]][2]-=minf;

        e[pre[cur]^1][2]+=minf;

        cur=prv[cur];

    }

    flow+=minf;

    sum+=d[t]*minf;

    return 1;

}

int mincost(int &flow)

{

    int sum=0;

   while(spfa(sum,flow));

    return sum;

}

void init()

{

    nume=0;

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

       head[i]=-1;

}

void read_build()

{

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

          scanf("%d",&froms[j]);

      int aa,bb,cc;

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

     {

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

        adde(aa,bb,inf,cc);

        adde(bb,aa,inf,cc);

     }

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

     {

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

        adde(bb,aa+m,inf,cc);

      //   adde(aa+m,bb,inf,cc);

     }

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

      {

          adde(0,froms[i],1,0);

          adde(m+1+i,n+m+1,1,0);

      }

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

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

       {

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

       }*/

}

int main()

{

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

    {

        init();

        read_build();

        int flow=0;

        int ans=mincost(flow);

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

    }

    return 0;

}

巴特西

hdu2448 / 费用流 / harbin赛区c题

最新文章

热门文章