【网络流】网络扩容

              【问题描述】
              	给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求:
              1、 在不扩容的情况下,1到N的最大流;
              2、 将1到N的最大流增加K所需的最小扩容费用。
              【输入格式】network.in
              	输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。
              	接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。
              【输出格式】network.out
              	输出文件一行包含两个整数,分别表示问题1和问题2的答案。
              【输入样例】
              5 8 2
              1 2 5 8
              2 5 9 9
              5 1 6 2
              5 1 1 8
              1 2 8 7
              2 5 4 9
              1 2 1 1
              1 4 2 1
              【输出样例】
              	13 19
              【数据规模】
              	30%的数据中,N<=100
              	100%的数据中,N<=1000,M<=5000,K<=10
              这是一道最大流加最小费用流的问题。

              最大流就不再多说了。

              求出了最大流之后有个残量网络,将这些边的费用设为0(原图中剩余的流量免费),重新加入一些边(前提是原图中有这些边,于是),流量为k,费用为扩容费用,再加一个超级源,连一条容量为k,费用为0的边(限制流量最大为k),最后求一次最小费用流即可。

              Accode:

              #include <cstdio>
              #include <cstdlib>
              #include <string>
              #include <algorithm>
              #define min(a, b) ((a) < (b) ? (a) : (b))
              #define max(a, b) ((a) > (b) ? (a) : (b))
              
              const char fi[] = "network.in";
              const char fo[] = "network.out";
              const int maxN = 1010;
              const int SIZE = 0x3ff;
              const int MAX = 0x3f3f3f3f;
              const int MIN = ~MAX;
              
              struct Edge
              {
                  int u, v, f, c;
                  Edge *next, *back;
              };
              
              Edge *edge[maxN];
              Edge *pre[maxN];
              bool mp[maxN][maxN];
              int w[maxN][maxN];
              int d[maxN];
              int cnt[maxN];
              int q[SIZE + 1];
              int n, m, K, S = 1, T, f, r;
              
              void init_file()
              {
                  freopen(fi, "r", stdin);
                  freopen(fo, "w", stdout);
                  return;
              }
              
              inline int getint()
              {
                  int res = 0; char tmp;
                  while (!isdigit(tmp = getchar()));
                  do res = (res << 3) + (res << 1) + tmp - '0';
                  while (isdigit(tmp = getchar()));
                  return res;
              }
              
              inline void insert(int u, int v, int f, int c)
              {
                  Edge *p = new Edge;
                  p -> u = u; p -> v = v;
                  p -> f = f; p -> c = c;
                  p -> next = edge[u];
                  edge[u] = p;
                  p = new Edge;
                  p -> u = v; p -> v = u;
                  p -> f = 0; p -> c = -c;
                  p -> next = edge[v];
                  edge[v] = p;
                  edge[u] -> back = edge[v];
                  edge[v] -> back = edge[u];
                  return;
              }    
              
              void readdata()
              {
                  T = n = getint(); m = getint(); K = getint();
                  for (; m; --m)
                  {
                      int u = getint(), v = getint(),
                      f = getint(), c = getint();
                      mp[u][v] = 1;
              	//先用mp数组记录一下原图中有哪些边。
                      w[u][v] = w[u][v] ? min(w[u][v], c) : c;
              	//记录扩容费用。
                      insert(u, v, f, 0);
                  }
                  return;
              }
              
              int Sap(int u, int Lim)
              {
                  if (u == T) return Lim;
                  int tmp = 0;
                  for (Edge *p = edge[u]; p; p = p -> next)
                  if (p -> f > 0 && d[u] == d[p -> v] + 1)
                  {
                      int k = Sap(p -> v, min(p -> f, Lim - tmp));
                      p -> f -= k;
                      p -> back -> f += k;
                      if ((tmp += k) == Lim) return tmp;
                  }
                  if (d[S] >= n) return tmp;
                  if ((--cnt[d[u]]) == 0) d[S] = n;
                  ++cnt[++d[u]];
                  return tmp;
              }
              
              int Spfa()
              {
                  memset(pre, 0, sizeof pre);
                  memset(d, 0x3f, sizeof d);
                  memset(cnt, 0, sizeof cnt);
                  f = r = 0;
                  d[S] = 0;
                  ++cnt[q[r++] = S];
                  r &= SIZE;
                  while (f != r)
                  {
                      int u = q[f++];
                      f &= SIZE;
                      --cnt[u];
                      for (Edge *p = edge[u]; p; p = p -> next)
                      if (p -> f > 0)
                      {
                          int v = p -> v;
                          int c = p -> c;
                          if (d[u] + c < d[v])
                          {
                              d[v] = d[u] + c;
                              pre[v] = p;
                              if (!cnt[v])
                              {
                                  ++cnt[q[r++] = v];
                                  r &= SIZE;
                              }
                          }
                      }
                  }
                  return pre[T] != NULL;
              }
              
              int min_fee()
              {
                  int ans = 0;
                  while (Spfa())
                  {
                      int max_flow = MAX;
                      for (Edge *p = pre[T]; p; p = pre[p -> u])
                          max_flow = min(max_flow, p -> f);
                      for (Edge *p = pre[T]; p; p = pre[p -> u])
                      {
                          p -> f -= max_flow;
                          p -> back -> f += max_flow;
                      }
                      ans += d[T] * max_flow;
                  }
                  return ans;
              }
              
              void work()
              {
                  int ans = 0;
                  cnt[0] = n;
                  while (d[S] < n) ans += Sap(S, MAX);
                  for (int u = 1; u < n + 1; ++u)
                  for (int v = 1; v < n + 1; ++v)
                      if (mp[u][v]) insert(u, v, MAX, w[u][v]);
                  insert(S = 0, 1, K, 0);
                  printf("%d %d\n", ans, min_fee());
                  return;
              }
              
              int main()
              {
                  init_file();
                  readdata();
                  work();
                  return 0;
              }
              
              #undef min
              #undef max
              再贴一个求费用流时没有退流的骗分程序,能过90分。
              #include <cstdio>
              #include <cstdlib>
              #include <string>
              #include <algorithm>
              #define min(a, b) ((a) < (b) ? (a) : (b))
              #define max(a, b) ((a) > (b) ? (a) : (b))
              
              const char fi[] = "network.in";
              const char fo[] = "network.out";
              const int maxN = 1010;
              const int SIZE = 0x3ff;
              const int MAX = 0x3f3f3f3f;
              const int MIN = ~MAX;
              
              struct Edge
              {
                  int u, v, f, c;
                  Edge *next, *back;
              };
              
              Edge *edge[maxN];
              int d[maxN];
              int cnt[maxN];
              int q[SIZE + 1];
              int n, m, K, S = 1, T, f, r;
              
              void init_file()
              {
                  freopen(fi, "r", stdin);
                  freopen(fo, "w", stdout);
                  return;
              }
              
              inline int getint()
              {
                  int res = 0; char tmp;
                  while (!isdigit(tmp = getchar()));
                  do res = (res << 3) + (res << 1) + tmp - '0';
                  while (isdigit(tmp = getchar()));
                  return res;
              }
              
              inline void insert(int u, int v, int f, int c)
              {
                  for (Edge *p = edge[u]; p; p = p -> next)
                  if (p -> v == v)
                  {
                      p -> f += f;
                      p -> c = min(p -> c, c);
                      return;
                  }
                  Edge *p = new Edge;
                  p -> u = u; p -> v = v;
                  p -> f = f; p -> c = c;
                  p -> next = edge[u];
                  edge[u] = p;
                  p = new Edge;
                  p -> u = v; p -> v = u;
                  p -> f = 0;
                  p -> c = MAX;
                  p -> next = edge[v];
                  edge[v] = p;
                  edge[u] -> back = edge[v];
                  edge[v] -> back = edge[u];
                  return;
              }
              
              void readdata()
              {
                  T = n = getint(); m = getint(); K = getint();
                  for (; m; --m)
                  {
                      int u = getint(), v = getint(),
                      f = getint(), c = getint();
                      insert(u, v, f, c);
                  }
                  return;
              }
              
              int Sap(int u, int Lim)
              {
                  if (u == T) return Lim;
                  int tmp = 0;
                  for (Edge *p = edge[u]; p; p = p -> next)
                  if (p -> f > 0 && d[u] == d[p -> v] + 1)
                  {
                      int k = Sap(p -> v, min(p -> f, Lim - tmp));
                      p -> f -= k;
                      p -> back -> f += k;
                      if ((tmp += k) == Lim) return tmp;
                  }
                  if (d[S] >= n) return tmp;
                  if ((--cnt[d[u]]) == 0) d[S] = n;
                  ++cnt[++d[u]];
                  return tmp;
              }
              
              int Spfa()
              {
                  memset(d, 0x3f, sizeof d);
                  memset(cnt, 0, sizeof cnt);
                  d[S] = 0;
                  ++cnt[q[r++] = S];
                  r &= SIZE;
                  while (f != r)
                  {
                      int u = q[f++];
                      f &= SIZE;
                      --cnt[u];
                      for (Edge *p = edge[u]; p; p = p -> next)
                      if (p -> c < MAX)
                      {
                          int v = p -> v;
                          int c = (p -> c) * max(0, K - p -> f);
                          if (d[u] + c < d[v])
                          {
                              d[v] = d[u] + c;
                              if (!cnt[v])
                              {
                                  ++cnt[q[r++] = v];
                                  r &= SIZE;
                              }
                          }
                      }
                  }
                  return d[T];
              }
              
              void work()
              {
                  int ans = 0;
                  cnt[0] = n;
                  while (d[S] < n) ans += Sap(S, MAX);
                  printf("%d %d\n", ans, K ? Spfa() : 0);
                  return;
              }
              
              int main()
              {
                  init_file();
                  readdata();
                  work();
                  return 0;
              }
              
              #undef min
              #undef max
              相关文章
              相关标签/搜索
              香港蓝月亮精选免费资料大全管家婆王中王鉄算盘开奖结果2019开奖记录结果查询香港马会开奖结果历史纪录在线查询 土默特右旗| 合作市| 连城县| 万源市| 邛崃市| 甘谷县| 黑河市| 贡山| 丰都县| 宁安市| 团风县| 济阳县| 津市市| 汝南县| 阜新市| 清丰县| 惠安县| 广昌县| 合山市| 大荔县| 马尔康县| 汤原县| 莆田市| 舞钢市| 北碚区| 昔阳县| 庆云县| 通城县| 太湖县| 邵阳市| 海安县| 江都市| 乌鲁木齐市| 红安县| 长武县| 多伦县| 来宾市| 濮阳县| 建瓯市| 林西县| 太康县| 枣阳市| 凤城市| 巴里| 报价| 绍兴市| 宜昌市| 紫阳县| 平定县| 萝北县| 兖州市| 城固县| 轮台县| 宣武区| 嘉义县| 枞阳县| 朝阳区| 谷城县| 滦南县| 乌苏市| 公主岭市| 亚东县| 肇东市| 商洛市| 陆川县| 京山县| 青浦区| 江华| 义马市| 仪征市| 额敏县| 祁阳县| 阿瓦提县| 玉溪市| 漳浦县| 博爱县| 清水县| 花莲县| 南京市| 古田县| 垣曲县| 金川县| 洛阳市| 阳原县| 格尔木市| 两当县| 濮阳县| 赤城县| 乾安县| 云阳县| 凤翔县| 报价| 武平县| 涪陵区| 大田县| 海伦市| 葵青区| 类乌齐县| 罗城| 桃园县| 德阳市| 高台县| 融水| 高安市| 云和县| 偏关县| 扬中市| 乾安县| 水富县| 潼关县| 鹿泉市| 东源县| 永济市| 灵宝市| 潼关县| 嫩江县| 呈贡县| 镇沅| 武义县| 青州市| 永春县| 新疆| 岐山县| 金昌市| 博白县| 定南县| 惠来县| 申扎县| 根河市| 霍州市| 虹口区| 宁德市| 张家界市| 彭州市| 庆阳市| 仪陇县| 靖安县| 四子王旗| 广德县| 乐山市| 灌南县| 新丰县| 洱源县| 中江县| 那坡县| 宜州市| 婺源县| 衡阳市| 南陵县| 温泉县| 息烽县| 龙泉市| 黄冈市| 泽普县| 福建省| 惠州市| 盐边县| 屯留县| 安丘市| 韶山市| 松滋市| 诸城市| 湖北省| 河池市| 平和县| 灵寿县| 和平县| 科尔| 新和县| 芜湖市| 灵丘县| 双峰县| 广南县| 广河县| 六盘水市| 象山县| 怀集县| 长顺县| 桐梓县| 桃源县| 襄垣县| 普安县| 哈尔滨市| 福清市| 阳泉市| 常德市| 阿合奇县| 花莲市| 巴彦淖尔市| 盐边县| 湛江市| 微山县| 香河县| 玛纳斯县| 郧西县| 盘山县| 汽车| 黄骅市| 平武县| 霍林郭勒市| 崇礼县| 望江县| 沂水县| 萝北县| 崇仁县| 南昌市| 莆田市| 长治县| 安多县| 淄博市| 安泽县| 增城市| 乌什县| 义乌市| 沐川县| 陇南市| 漳州市| 揭东县| 澄迈县| 富宁县| 洪雅县| 东源县| 郓城县| 璧山县| 南丰县| 凯里市| 芜湖市| 汉源县| 永平县| 金山区| 泰安市| 临夏市| 东莞市| 哈尔滨市| 土默特左旗| 黑龙江省| 星座| 兴化市| 禄丰县| 黑河市| 漳浦县| 彭山县| 顺平县| 余干县| 商水县| 临洮县| 搜索| 虎林市| 钦州市| 西峡县| 长宁区| 黄龙县| 临桂县| 辽源市| 日土县| 南漳县| 黄龙县| 甘谷县| 金川县| 南充市| 新密市| 泉州市| 德州市| 封丘县| 丽水市| 苗栗县| 柳江县| 通化市| 通渭县| 兴和县| 静海县| 玉环县| 裕民县| 宿迁市| 来安县| 潞城市| 辽源市| 河北省| 勐海县| 喜德县| 江阴市| 离岛区| 宿州市| 尼玛县| 德兴市| 开远市| 行唐县| 嘉兴市| 即墨市| 永城市| 天等县| 惠来县| 北碚区| 宜州市| 个旧市| 金堂县| 抚顺市| 中山市| 兰溪市| 廊坊市| 江油市| 柘荣县| 当雄县| 黔南| 宾川县| 瓦房店市| 海晏县| 喀喇沁旗| 吉隆县| 卓尼县| 金溪县| 大名县| 谢通门县| 阳曲县| 合作市| 六安市| 兰坪| 香河县| 齐河县| 静宁县| 溧阳市| 桐乡市| 锦州市| 尤溪县| 休宁县| 赤峰市| 通州区| 东安县| 正安县| 繁峙县| 濮阳市| 乌鲁木齐县| 临桂县| 堆龙德庆县| 敦化市| 武陟县| 海南省| 富顺县| 汉川市| 奉新县| 许昌县| 营口市| 垫江县| 南皮县| 富宁县| 屯留县| 永登县| 崇仁县| 宜兰县| 临夏市| 八宿县| 恩平市| 修武县| 瑞昌市| 巴林右旗| 子洲县| 新源县| 新郑市| 南通市| 阿克陶县| 安达市| 都兰县| 鹿泉市| 开封县| 贵港市| 留坝县| 根河市| 榆树市| 定州市| 寿阳县| 弥渡县| 璧山县| 东阿县| 大同市| 米脂县| 广南县| 怀化市| 蓝田县| 磐石市| 凭祥市| 荣昌县| 丹巴县| 红河县| 五家渠市| 雅江县| 罗源县| 新绛县| 和平区| 徐水县| 内江市| 中方县| 山西省| 栾川县| 辰溪县| 元朗区| 鸡东县| 河池市| 陆丰市| 巫山县| 遂宁市| 义马市| 仙游县| 额尔古纳市| 齐齐哈尔市| 和硕县| 岳普湖县| 怀远县| 中江县| 沿河| 青河县| 哈尔滨市| 电白县| 洞口县| 泽库县| 额敏县| 米林县| 张家界市| 无为县| 顺平县| 丹棱县| 光山县| 光泽县| 工布江达县| 白玉县| 秀山| 建平县| 梅州市| 通州区| 化德县| 吉木乃县| 清涧县| 奈曼旗| 柞水县| 钟山县| 岱山县| 神池县| 华池县| 齐河县| 定州市| 宝兴县| 定结县| 南宫市| 七台河市| 镇沅| 乐至县| 全州县| 石渠县| 名山县| 永福县| 潜山县| 邯郸市| 绥德县| 武平县| 昌吉市| 修武县| 屏边| 牙克石市| 平果县| 玛曲县| 青铜峡市| 本溪| 格尔木市| 渝北区| 大渡口区| 肃宁县| 临夏县| 确山县| 昌平区| 江川县| 大荔县| 青州市| 东源县| 永宁县| 涟水县| 绩溪县| 无棣县| 嘉禾县| 固始县| 衡阳市| 乐业县| 钟祥市| 鄢陵县| 盖州市| 平江县| 三河市| 平武县| 涞源县| 铜川市| 栖霞市| 铁力市| 鄄城县| 莱西市| 屯昌县| 肃宁县| 内丘县| 昌宁县| 临朐县| 舞阳县| 东丰县| 阿拉善盟| 兴海县| 巫山县| 东光县| 台前县| 云龙县| 微博| 西和县| 普兰店市| 陵川县| 阿巴嘎旗| 赤峰市| 依安县| 班戈县| 九龙县| 泰顺县| 桓仁| 姜堰市| 泾川县| 高邑县| 乐陵市| 罗甸县| 离岛区| 寿宁县| 荥经县| 碌曲县| 阿拉尔市| 安塞县| 革吉县| 林西县| 锡林郭勒盟| 新沂市| 陕西省| 正镶白旗| 佛坪县| 沁源县| 磴口县| 诸暨市| 云梦县| 淮滨县| 盐边县| 青海省| 固始县| 衡南县| 龙泉市| 彰化县| 昭苏县| 南陵县| 四子王旗| 双江| 巨鹿县| 会昌县| 威信县| 林周县| 灵台县| 乌拉特中旗| 永城市| 井研县| 永善县| 水富县| 富平县| 聂荣县| 西昌市| 桓台县| 西安市| 东阳市| 贵定县| 鄂托克前旗| 临江市| 万州区| 阿巴嘎旗| 荆州市| 安龙县| 巨野县| 雅江县| 德阳市| 新野县| 河北区| 天气| 枣庄市| 鸡泽县| 恭城| 兰西县| 班戈县| 涟水县| 仙桃市| 思茅市| 育儿| 依安县| 磐安县| 宁陵县| 安徽省| 门源| 兰溪市| 文安县| 南阳市| 涟水县| 赫章县| 龙游县| 元氏县| 县级市| 青阳县| 汝阳县| 淮阳县| 大姚县| 增城市| 仁化县| 华蓥市| 阳东县| 广丰县| 台南县| 屯昌县| 民县| 台北县| 武汉市| 榕江县| http://m.jx1870izportv.fun http://wap.jx1870holev.fun http://m.jx1870experiencev.fun http://m.jx1870exchangev.fun http://m.jx1870furtherv.fun http://jx1870husbandv.fun http://www.jx1870insertv.fun http://wap.jx1870fundv.fun http://www.jx1870forzv.fun http://wap.hz0j4r6vo.fun http://m.jx1870includev.fun http://wap.jx1870juzpv.fun http://www.jx1870evidencev.fun http://www.jx1870helpv.fun http://wap.jx1870forestv.fun http://www.jx1870helpv.fun http://m.jx1870influencev.fun http://m.jx1870fearv.fun