hdu4309

题解：

暴力枚举

然后网络流

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int E=,V=,inf=0xffff;

struct Edge{int u,v,c,next;}edge[E];

int a,bb,c,d,p[V],r,b,t,n,m,cnt,cou,dist[V],head[V],que[V],fb[],sta[V];

void init()

{

    cnt=;

    memset(head,-,sizeof(head));

}

void jb(int u,int v,int c)

{

    edge[cnt].u=u;edge[cnt].v=v;edge[cnt].c=c;

    edge[cnt].next=head[u];head[u]=cnt++;

    edge[cnt].u=v;edge[cnt].v=u;edge[cnt].c=;

    edge[cnt].next=head[v];head[v]=cnt++;

}

int dinic(int s,int t)

{

    int ans=;

    while()

     {

        int left,right,u,v;

        memset(dist,-,sizeof(dist));

        left=right=;

        que[right++]=s;

        dist[s]=;

        while (left<right)

         {

            u=que[left++];

            for (int k=head[u];k!=-;k=edge[k].next)

             {

                u=edge[k].u;

                v=edge[k].v;

                if (edge[k].c> && dist[v]==-)

                 {

                    dist[v]=dist[u]+;

                    que[right++]=v;

                    if(v==t)

                     {

                        left=right;

                        break;

                     }

                 }

             }

         }

        if (dist[t]==-) break;

        int top=,now=s;

        while ()

         {

            if (now!=t)

             {

                int k;

                for (k=head[now];k!=-;k=edge[k].next)

                 if (edge[k].c>&&dist[edge[k].u]+==dist[edge[k].v]) break;

                if (k!=-)

                 {

                    sta[top++]=k;

                    now=edge[k].v;

                 }

                else

                 {

                    if (top==) break;

                    dist[edge[sta[--top]].v]=-;

                    now=edge[sta[top]].u;

                 }

             }

            else

             {

                int flow=inf,ebreak;

                for (int i=;i<top;i++)

                 if (flow>edge[sta[i]].c)

                  {

                    flow=edge[sta[i]].c;

                    ebreak=i;

                  }

                ans+=flow;

                for (int i=;i<top;i++)

                 {

                    edge[sta[i]].c-=flow;

                    edge[sta[i]^].c+=flow;

                 }

                now=edge[sta[ebreak]].u;

                top=ebreak;

             }

         }

     }

    return ans;

}

struct T{int u,v,c;}road[E],bridge[E],tunnel[E];

struct R{int num,cost;}res[E];

void build()

{

    init();

    for (int i=;i<=n;i++)jb(,i,p[i]);

    for (int i=;i<r;i++)jb(road[i].u,road[i].v,inf);

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

     {

        jb(tunnel[i].u,n+i+,inf);

        jb(n+i+,tunnel[i].v,inf);

        jb(n+i+,n+t+,tunnel[i].c);

     }

}

void dfs(int s)

{

    if (s==b)

     {

        int sum=;

        build();

        for (int i=;i<b;i++)

         {

            if (fb[i]==)

             {

                jb(bridge[i].u,bridge[i].v,);

                sum+=;

             }

            else

             {

                jb(bridge[i].u,bridge[i].v,inf);

                sum+=bridge[i].c;

             }

         }

        res[cou].num=dinic(,n+t+);

        res[cou++].cost=sum;

        return ;

     }

    fb[s]=;

    dfs(s+);

    fb[s]=;

    dfs(s+);

}

int main()

{

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

     {

        for (int i=;i<=n;i++)scanf("%d",&p[i]);

        r=b=t=;

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

         {

            scanf("%d%d%d%d",&a,&bb,&c,&d);

            if (d<)

             {

                tunnel[t].u=a;

                tunnel[t].v=bb;

                tunnel[t++].c=c;

             }

            if (d==)

             {

                road[r].u=a;

                road[r++].v=bb;

             }

            if (d>)

             {

                bridge[b].u=a;

                bridge[b].v=bb;

                bridge[b++].c=c;

             }

         }

        memset(fb,,sizeof(fb));

        for (int i=;i<;i++)res[i].cost=res[i].num=;

        cou=;dfs();

        int minc=inf,maxc=-;

        for (int i=;i<cou;i++)

         if (res[i].num>maxc)maxc=res[i].num;

        for (int i=;i<cou;i++)

         if (res[i].num==maxc)

          if (res[i].cost<minc)minc=res[i].cost;

        if (maxc==) puts("Poor Heaven Empire");

        else printf("%d %d\n",maxc,minc);

     }

    return ;

}