hdu3917 最大权闭合图-白红宇的个人博客

hdu3917 最大权闭合图

发布日期：2021-08-15 22:29:18 浏览次数：32 分类：技术文章

本文共 2496 字，大约阅读时间需要 8 分钟。

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

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

分析：

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

#include
     
      #include
      
       #include
       
        #define INF 99999999using namespace std;const int maxn = 6500;struct node{    int to;    int v;    int flag;    int next;}edge[maxn*maxn/2];struct company{    int x;    int y;    int t;    int z;}temp[3100];int index,pre[maxn],S,T,vis[maxn];int val[5050],fv[5050];int min(int x,int y){
   return x
        
         0&&vis[edge[i].to]==vis[u]+1)        {            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]=-1;    return used;}bool BFS(){    int i;    queue
         
          q;    memset(vis,-1,sizeof(vis));    vis[0]=1;    q.push(0);    while(!q.empty())    {        int t=q.front();        q.pop();        for(i=pre[t];i!=-1;i=edge[i].next)        {            if(edge[i].v&&vis[edge[i].to]<0)            {                vis[edge[i].to]=vis[t]+1;                q.push(edge[i].to);            }        }    }    if(vis[T]>0)        return true;    return false;}int main(){    int n,m,i,j,k;    while(~scanf("%d%d",&n,&m))    {        if(!n&&!m)            break;        int sum=0;        index=1;        memset(pre,-1,sizeof(pre));        memset(fv,0,sizeof(fv));        for(i=1;i<=m;i++)        {            scanf("%d",&val[i]);        }        scanf("%d",&k);        for(i=1;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=1;i<=m;i++)        {            if(val[i]<0)                add(i,m+1,-val[i]);            else            {                sum+=val[i];                add(0,i,val[i]);            }        }        for(i=1;i<=k;i++)        {            for(j=1;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=0;        S=0,T=m+1;        while(BFS())        {            int a=dfs(0,INF);            if(!a)break;            ans+=a;        }        printf("%d\n",sum-ans);    }}

转载于:https://www.cnblogs.com/sweat123/p/4920788.html

转载地址：https://blog.csdn.net/weixin_30781107/article/details/97088278 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：计算第K个素数

下一篇：百度前端学习日记05——页面布局（一）浮动

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章