Articles under the label of 最小费用最大流

  1.  Home
  2. 最小费用最大流

「网络流 24 题」航空路线问题

「网络流 24 题」航空路线问题题解：求两条最大权不相交路径，用map将城市string映射到城市编号i，然后将每个城市i拆成Xi和Yi并且连接一条容量为1，权值为0的边，然后从源点向第一个点连接容量为1，权值为0的边，输出好麻烦啊！#include <bits/stdc++.h> const int MAXN = 1000000,INF = 10000000; using ...

 285484026   October 25, 2018  No comments

「网络流 24 题」最长 k 可重区间集

「网络流 24 题」最长 k 可重区间集题解：题意是说选择出一个线段集合，使得任何一个点x含有的区间不超过K条，要求求出一个区间集合使得集合中所有区间长度相加的总长度最大#include <bits/stdc++.h> const int MAXN = 1000000,INF = 10000000; using namespace std; int n,k,s,t,e = ...

 285484026   October 25, 2018  No comments

「网络流 24 题」负载平衡

「网络流 24 题」负载平衡题解：从源点向每个物品大于平均值的的点连边权值为0，容量为data[i]-ans，然后从每个物品小于平均值的向汇点连边ans-data[i]，然后从每个点向相邻的两个点连容量为INF，权值为1的边#include <bits/stdc++.h> const int MAXN = 1000000,INF = 10000000; using names...

 285484026   October 25, 2018  No comments

「网络流 24 题」分配问题

「网络流 24 题」分配问题题解：一个最大费用最大流的模板题，只要将最小费用最大流的费用建图中的权值反过来建图，#include <bits/stdc++.h> const int MAXN = 5000000,INF = 10000000; using namespace std; int n,s,t,e1 = 2,e2 = 2; int head1[MAXN],head...

 285484026   October 25, 2018  No comments

「网络流 24 题」运输问题

「网络流 24 题」运输问题题解：一个简单的最小费用最大流的模板题#include <bits/stdc++.h> const int MAXN = 1000000,INF = 10000000; using namespace std; int n,sum,s,t,e = 2,cnt,ans; int data[MAXN],pos[MAXN],head[MAXN],pri...

 285484026   October 25, 2018  No comments