腾讯云wordpress建站教程,淘宝客app定制,做网站什么颜色和蓝色配,建设工程施工合同2017活动 - AcWing
给出一个带权无向图 G(V,E)#xff0c;每条边 e 有一个权 we。
求将点 s 和点 t 分开的一个边割集 C#xff0c;使得该割集的平均边权最小#xff0c;即最小化#xff1a;
∑(e∈C)we/|C|
注意#xff1a; 边割集的定义与最小割中的割边的集合不同。在本…活动 - AcWing
给出一个带权无向图 G(V,E)每条边 e 有一个权 we。
求将点 s 和点 t 分开的一个边割集 C使得该割集的平均边权最小即最小化
∑(e∈C)we/|C|
注意 边割集的定义与最小割中的割边的集合不同。在本题中一个边割集是指将这些边删去之后s 与 t 不再连通。
输入格式
第一行包含四个整数 n,m,s,t其中 n,m 分别表示无向图的点数、边数。
接下来 m 行每行包含三个整数 a,b,w表示点 a 和 b 之间存在一条无向边边权为 w。
点的编号从 1 到 n。
输出格式
输出一个实数表示将点 s 和点 t 分开的边割集的最小平均边权。
结果保留两位小数。
数据范围
2≤n≤100, 1≤m≤400, 1≤w≤107 保证 s 和 t 之间连通。
输入样例
6 8 1 6
1 2 3
1 3 3
2 4 2
2 5 2
3 4 2
3 5 2
5 6 3
4 6 3输出样例
2.00
解析
01分数规划上一篇题解有详细讲解361. 观光奶牛小数二分spfa判断正环01分数规划-CSDN博客。 本题要求的是∑(e∈C)we/|C| 的最小值。这种形式的问题基本都需要用到 01 分数规划。 现在取一个值 x然后我们看一下 ∑(e∈C)we/|C| 和 x 的关系。 假设现在 ∑(e∈C)we/|C|x通过变形得到 ∑(e∈C)we−|C|⋅x0由于 ∑e∈Cwe 和 x 都有 |C| 个因此进一步化简为 ∑e∈C(we−x)0。 假设现在 ∑e∈Cwe|C|x同样可以得到 ∑e∈C(we−x)0。 因此我们可以根据 ∑e∈C(we−x) 和 0 的关系来判断 ∑e∈Cwe|C| 和 x 的关系。而这个关系是有二段性的是可以进行二分的。 在整个范围区间内进行二分二分出的中间值就是 x如果 ∑e∈C(we−x)0说明∑e∈Cwe|C|x继续二分右区间。否则说明 ∑e∈Cwe|C|x继续二分左区间。最终得到一个固定值就是答案。 每次需要求出 ∑e∈C(we−x)我们可以建一个新图将所有边都减去 x在新图中求一个边割集的权值和就是 ∑e∈C(we−x)。 那么新图中可能存在 we−x≤0对于这样的边我们一定要选上因为一个边割集若加上一些无法让图重新连上的边它仍然是一个边割集但是权值和会变小所以这种负权值边必选。 现在已经选上所有非正边我们需要考虑一下剩下的边该怎么选因为边割集和流网络的割是不一样的边割集在有流网络的割的所有边的同时在这两个集合里面还有一些边这些边去掉之后也能让整张图不连通由于剩下要考虑的边都是正边我们要让权值和越小因此这两个集合里面的边尽量能不选就不选因此在权值和最小的情况下边割集一定不包含所有集合里面的边了这时就是只剩下两个集合之间的边了而这些边的权值和其实就是流网络的割。 通过以上的分析我们成功将每个边割集的权值和与流网络的割的边的容量和对应起来。而边割集的最小权值和就是割的最小容量和即最小割。 然后本题是无向图而流网络中是有向图我们需要将有向图和无向图对应起来我们只需要正常建两条有向边来回的流量会被抵消而且流网络的割有一个特点就是保证正向边是满流反向边是 0 流所以无向图的割等价于有向图的割不需要额外处理。 然后这里每条无向边建两条有向边有向边在残量网络中又有反向边所以每条无向边都要建四条边这里和前面的某一题一样直接合并成两条边即可。 最终得出本题算法二分找最小值每次求一遍最小割继续二分。 作者小小_88 链接https://www.acwing.com/solution/content/128176/ 来源AcWing 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 #includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
const int N 1e4 5, M 1e5 * 2 10, INF 0x3f3f3f3f;
const double eps 1e-8;
int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;e[idx] a, w[idx] c, ne[idx] h[b], h[b] idx;
}bool bfs() {int hh 0, tt 0;memset(d, -1, sizeof d);q[0] S, d[S] 0, cur[S] h[S];while (hh tt) {int t q[hh];for (int i h[t]; i ! -1; i ne[i]) {int j e[i];if (d[j] -1 f[i]) {d[j] d[t] 1;cur[j] h[j];if (j T)return 1;q[tt] j;}}}return 0;
}double find(int u, double limit) {if (u T)return limit;double flow0;for (int i cur[u]; i ! -1 flow limit; i ne[i]) {int j e[i];cur[u] i;if (d[j] d[u] 1 f[i]) {double t find(j, min(limit - flow, f[i]));if (!t)d[j] -1;f[i] - t, f[i ^ 1] t, flow t;}}return flow;
}double dinic(double mid) {double ret 0;for (int i 0; i idx; i 2) {if (w[i] mid) {ret w[i] - mid;f[i] f[i ^ 1] 0;}else f[i] f[i ^ 1] w[i] - mid;}double r 0, flow;while (bfs())while (flow find(S, INF))r flow;return r ret;
}int main() {cin n m S T;memset(h, -1, sizeof h);for (int i 1,a,b,c; i m; i) {scanf(%d%d%d, a, b, c);add(a, b, c);}double l 0, r 1e7;double mid;while (r - l eps) {mid (r l) / 2;if (dinic(mid) 0)r mid;else l mid;}printf(%.2lf\n, r);return 0;
}
