Orz胡伯涛《最小割模型在信息学竞赛中的应用》

建图方法:

设立源点S和汇点T,S和用户(共M个)连边,载流量为满足其要求的获利

T和中转站(共N个)连边,载流量为建立该中转站的费用

每个用户向对应的2个中转站连边,载流量为inf

对该图跑一遍最大流,求出最小割f,(∑Ci)-f就是答案

 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <queue>

 ;
 ;
 const int inf=0x3f3f3f3f;

 struct Edge
 {
     int to,next;
     int capacity;

     void assign(int t,int n,int c)
         { to=t; next=n; capacity=c; }
 };

 Edge elist[*maxE];
 int head[maxV];
 int ecnt;

 void initEdge()
 {
     memset(head,-,sizeof(head));
     ecnt=;
 }

 inline void addEdge(int from,int to,int capacity)
 {
     elist[ecnt].assign(to,head[from],capacity);
     head[from]=ecnt++;
     elist[ecnt].assign();
     head[to]=ecnt++;
 }

 int N,M;
 int tot;
 int sink; //1~M:user M+1~N:station

 void input()
 {
     scanf("%d%d",&N,&M);
     initEdge();
     sink=N+M+;
     int cost;
     ;i<=N;i++)
     {
         scanf("%d",&cost);
         addEdge(M+i,sink,cost);
     }
     tot=;
     int v1,v2;
     ;i<=M;i++)
     {
         scanf("%d%d%d",&v1,&v2,&cost);
         tot+=cost;
         addEdge(i,M+v1,inf);
         addEdge(i,M+v2,inf);
         addEdge(,i,cost);
     }
 }

 int layer[maxV];
 std::queue<int> que;

 bool bfs()
 {
     memset(layer,,sizeof(layer));
     layer[]=;
     que.push();
     while(!que.empty())
     {
         int cur=que.front();
         que.pop();
         ;e=elist[e].next)
         {
             int& to=elist[e].to;
             int& cp=elist[e].capacity;
             if(!layer[to] && cp)
             {
                 layer[to]=layer[cur]+;
                 que.push(to);
             }
         }
     }
     return layer[sink];
 }

 int dfs(int cur,int flow)
 {
     if(cur==sink) return flow;
     );
     ;e=elist[e].next)
     {
         int& to=elist[e].to;
         int& cp=elist[e].capacity;
          && cp)
         {
             int tp=dfs(to,std::min(flow,cp));
             res+=tp; flow-=tp;
             elist[e].capacity-=tp;
             elist[e^].capacity+=tp;
             if(!flow) return res;
         }
     }
     return res;
 }

 int dinic()
 {
     );
     ,inf);
     return res;
 }

 int main()
 {
     input();
     printf("%d\n",tot-dinic());
     ;
 }

最新文章

  1. MindManager中发送导图给别的用户的教程
  2. Python特殊语法--filter、map、reduce、lambda
  3. IOS之推送通知(本地推送和远程推送)
  4. Nginx环境中如何将HTTP跳转至HTTPS设置
  5. JavaScript Scoping and Hoisting
  6. How To Install Tinc and Set Up a Basic VPN on Ubuntu 14.04
  7. C# websocket Server 加密 76号协议
  8. POJ 3368 Frequent values RMQ 训练指南 好题
  9. [原创作品]手把手教你怎么写jQuery插件
  10. 基于Spring Cloud和Netflix OSS 构建微服务-Part 1
  11. .32-浅析webpack源码之doResolve事件流(4)
  12. SVN搭建外网远程访问
  13. win10系统电脑常用基本操作快捷键
  14. 配置supervisor管理beego应用
  15. python的mutable变量与immutable变量
  16. PTA L2-002 链表去重
  17. vue 2.0 vue.set的使用方法
  18. pgbench 安装试用
  19. OpenLayers 3 扩展插件收集
  20. brew || yarn 软件包管理工具

热门文章

  1. 挖坑#3-----DP优化+CDQ分治+期望DP
  2. 【转】 学习ios(必看经典)牛人40天精通iOS开发的学习方法【2015.12.2
  3. 元素重叠及position定位的z-index顺序
  4. java 解析xml文件案例
  5. MenuDrawer的使用
  6. C# ToString格式大全
  7. oracle REPLACE 函数 介绍
  8. SpringMVC DispatcherServlet 说明与web配置
  9. 支持MySql的数据库自动分表工具DBShardTools发布
  10. POJ 3277 City Horizon