hdu3917 最大权闭合图

题意：有N个城市，M个公司。现在需要建立交通是获得的利益最大。如果2个公司A,B, A修的路为Xa->Ya,B的路为Xb->Yb,如果Ya==Xb，那么这2个公司有关系。

对于每个公司都有获得的税，和需要付出的价值。求最大能够得到的利润为多少。

分析：

很明显是最小权闭合图。最大获利=总共的值-（付出的值+没得到的值）。

#include<stdio.h>

#include<string.h>

#include<queue>

#define INF 99999999

using namespace std;

const int maxn = ;

struct node

{

    int to;

    int v;

    int flag;

    int next;

}edge[maxn*maxn/];

struct company

{

    int x;

    int y;

    int t;

    int z;

}temp[];

int index,pre[maxn],S,T,vis[maxn];

int val[],fv[];

int min(int x,int y){return x<y?x:y;}

void add(int x,int y,int z)

{

    edge[index].to=y;

    edge[index].v=z;

    edge[index].flag=index+;

    edge[index].next=pre[x];

    pre[x]=index++;

    edge[index].to=x;

    edge[index].v=;

    edge[index].flag=index-;

    edge[index].next=pre[y];

    pre[y]=index++;

}

int dfs(int u,int low)

{

    int i,used=;

    if(u==T)

        return low;

    for(i=pre[u];i!=-&&used<low;i=edge[i].next)

    {

        if(edge[i].v>&&vis[edge[i].to]==vis[u]+)

        {

            int a=dfs(edge[i].to,min(edge[i].v,low-used));

            edge[i].v-=a;

            edge[edge[i].flag].v+=a;

            used+=a;

        }

    }

    if(!used)

        vis[u]=-;

    return used;

}

bool BFS()

{

    int i;

    queue<int>q;

    memset(vis,-,sizeof(vis));

    vis[]=;

    q.push();

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        for(i=pre[t];i!=-;i=edge[i].next)

        {

            if(edge[i].v&&vis[edge[i].to]<)

            {

                vis[edge[i].to]=vis[t]+;

                q.push(edge[i].to);

            }

        }

    }

    if(vis[T]>)

        return true;

    return false;

}

int main()

{

    int n,m,i,j,k;

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

    {

        if(!n&&!m)

            break;

        int sum=;

        index=;

        memset(pre,-,sizeof(pre));

        memset(fv,,sizeof(fv));

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

        {

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

        }

        scanf("%d",&k);

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

        {

            scanf("%d%d%d%d",&temp[i].x,&temp[i].y,&temp[i].t,&temp[i].z);

            val[temp[i].t]-=temp[i].z;

        }

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

        {

            if(val[i]<)

                add(i,m+,-val[i]);

            else

            {

                sum+=val[i];

                add(,i,val[i]);

            }

        }

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

        {

            for(j=;j<=k;j++)

            {

                if(i==j)continue;

                if(temp[i].y==temp[j].x)

                {

                    if(temp[i].t!=temp[j].t)

                    {

                        add(temp[i].t,temp[j].t,INF);

                    }

                }

            }

        }

        int ans=;

        S=,T=m+;

        while(BFS())

        {

            int a=dfs(,INF);

            if(!a)break;

            ans+=a;

        }

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

    }

}

巴特西

hdu3917 最大权闭合图

最新文章

热门文章