博客首页 → 网络流

最新文章列表

[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292：Food

大致题意：     有F种食物和D种饮料，每种食物或饮料只能供有限次，且每个人只享用一种食物和一种饮料。现在有n头牛，每个人都有自己喜欢的食物种类列表和饮料种类列表，问最多能使几个人同时享用到自己喜欢的食物和饮料。   大致思路：     把人给拆点，把食物和水的点放在人的两侧 求出s到t的网络流即可     #include<iostream> #include& ...
成都网络赛acm网络流bbezxcy图论 
暴风雪 评论(11) 有2351人浏览 2012-09-16 17:15

[网络流]2012 acm/icpc成都网络赛hdoj 4288：Control

大致题意：    给出一个又n个点，m条边组成的无向图。给出两个点s，t。对于图中的每个点，去掉这个点都需要一定的花费。求至少多少花费才能使得s和t之间不连通。   大致思路：    最基础的拆点最大流，把每个点拆作两个点 i 和 i' 连接i->i'费用为去掉这个点的花费，如果原图中有一条边a->b则连接a'->b。对这个图求出最大流即可。     #include&l ...
2012成都网络赛acmhdoj网络流 
暴风雪 评论(0) 有1363人浏览 2012-09-16 17:03

POJ 1459 Power Network 网络流基础题

题意： 输入：N个点，N1个发电厂，N2个用电厂,M条路。 输入M条路，s,e,l.代表点s-e的容量是l。 输入N1个发电厂，s,l.代表s产生l的电。 输入N2个用电产，s,l，代表s用掉l的电。 Sample Input 2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20 7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0) ...
网络流 
weirenhaojiu 评论(0) 有9人浏览 2012-08-18 21:53

SPOJ 371 Boxes

题意就是 有一些盒子，放在一个圈上，每个盒子中有若干个球，球的总数不会比盒子的数量多。 现在规定相邻的盒子之间可以把球移动过去，每次可以移动一个球，问用最少的步骤使得每个盒子中的球不超过1个 那么建图还是比较简单 源点跟每个点连接，容量为本来拥有的球数 每个点再与汇点连，容量为1 中间相邻的点之间连边，容量无穷，费用为1 #include <iost ...
网络流 
hongqiang 评论(0) 有983人浏览 2012-08-08 18:56

POJ 3422 最小费用最大流 zkw或者普通版本

建图的话 每个点拆成两个点u, u'，连一条容量为1费用为金币数的边，再连一条容量为k，费用为0的边 然后每个点和他右边或者下边的点连边 i'->j这样连 然后源点连1点，右下角那个点去连汇点，容量都为k，费用为0 普通写法 #include <iostream>#include <algorithm>#include <cstring>#in ...
网络流 
dayandn 评论(0) 有23人浏览 2012-08-08 13:38

POJ 3422 最小费用最大流 zkw或者普通版本

建图的话 每个点拆成两个点u, u'，连一条容量为1费用为金币数的边，再连一条容量为k，费用为0的边 然后每个点和他右边或者下边的点连边 i'->j这样连 然后源点连1点，右下角那个点去连汇点，容量都为k，费用为0 普通写法 #include <iostream>#include <algorithm>#include <cstring>#in ...
网络流 
wsp_java 评论(0) 有14人浏览 2012-08-08 13:16

[最大流]zoj 3305：Get Sauce

大致题意：     有n种原材料，每种一件。现在给出m个组合，每个组合包含k种原材料，代表这k种材料可以加工成一个成品。求最多能加工出多少成品。   大致思路：     先把每个点拆做a和a'。连接a->a'。设容量为1。对于每k个原材料，每个点a连接他后面的那个数拆出的点b‘。k个数中的头和尾分别连接到原点和汇点上。求出最大流即可。       吐槽一句，想出构图之后，又手贱看了 ...
网络流acmzoj 3305bbezxcy 
暴风雪 评论(0) 有979人浏览 2012-06-19 10:04

[网络流]hdoj 3251：Being a Hero

大致题意：    给出一个由n个点，m条边组成的有向图，给出切掉每条边的花费。给出f个点和得到这个点的收益值。现在要割掉一些边是的1点和某些城市分开，同时你会得到相应的收益值。求总收益的最大值。   大致思路：     网络流经典构图……   #include<iostream> #include<cstring> #include<cstdio&g ...
网络流hdoj 3251acm数据结构图论 
暴风雪 评论(0) 有1121人浏览 2012-03-22 16:15

[并查集+混合图欧拉回路+网络流]hdoj 3472：HS BDC

大致题意：     给出你n个单词，如果一个单词的尾部和另一个单词的头部相同那么这两个单词就能连在一起(比如‘abc’和‘cde’就能够连成abc-cde)，如果这个单词后面的数字是1，则代表这个单词的逆序也是一个单词，可以翻转过来。求所有单词能不能连成一长串。   大致思路：    转化为混合图的欧拉回路，把字母当作节点。注意要用并查集来检测图是否连通。   #include< ...
并查集混合图欧拉回路网络流hdoj 3472acm 
暴风雪 评论(0) 有1199人浏览 2012-03-02 18:33

【最大流+dinic+二分枚举】北大 poj 3189 Steady Cow Assignment

/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://poj.or ...
最大流网络流dinic二分 
panyanyany 评论(0) 有1023人浏览 2012-02-13 21:23

【最大流+dinic+二分】北大 poj 2455 Secret Milking Machine

/* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://poj.or ...
c++网络流最大流dinic 
panyanyany 评论(0) 有1190人浏览 2012-02-12 21:55

【最大流+Dinic+Edmonds_Karp+二分匹配】北大 poj 1698 Alice's Chance

Dinic 算法   /* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : ht ...
网络流最大流Edmonds_Karpdinic二分匹配 
panyanyany 评论(0) 有1818人浏览 2012-01-28 14:02

【最大流+模板题】杭电 hdu 3549 Flow Problem

    /* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu. ...
网络流最大流acm 
panyanyany 评论(0) 有1621人浏览 2012-01-04 00:45

【最大流】北大 poj 1274 The Perfect Stall

  /* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/ ...
网络流acmpku 
panyanyany 评论(0) 有1546人浏览 2012-01-01 17:54

【最大流】北大 poj 1273 Drainage Ditches

  /* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/ ...
网络流pkuacm 
panyanyany 评论(0) 有1083人浏览 2012-01-01 16:15

最近博客热门TAG

Java(141746) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics