AcWing2279 网络战争（01分数规划+网络流最小割模型）

旧城等待， 2022-10-25 04:54 125阅读 0赞

原题链接：[AcWing2279 网络战争][AcWing2279]

### 题目大意 ###

给一个无向带权图，求将s和t分开的一个边割集，使得**割集的平均边权**最小，即最小化 ∑ e ∈ c w e ∣ c ∣ \\frac\{\\sum\_\{e\\in c\} w\_e\}\{|c|\} ∣c∣∑e∈cwe。

### 思路 ###

见到最小化平均值，就会想到[二分模型][Link 1]，然后我们就判断这个值有没有二段性，能否用二分。又看到求和除以数量，就想到[01分数规划][01]。  
假设ans是原式的最小值，则 ∑ e ∈ c w e ∣ c ∣ = a n s \\frac\{\\sum\_\{e\\in c\} w\_e\}\{|c|\}= ans ∣c∣∑e∈cwe=ans，经过化简， ∑ ( w e − a n s ) = 0 \\sum (w\_e - ans)= 0 ∑(we−ans)=0，然后我们二分找ans即可，然后最重要的就是这个判断函数我们怎么写，怎么去计算 ∑ ( w e − a n s ) \\sum (w\_e - ans) ∑(we−ans)，这里我们就需要用[网络流][Link 2]，借助最小割模型，将该问题中的每一种情况都对应到流网络的一种割，则最小值就是最小割。  
我们将原图中的每一条边都减去ans，得到一个新图G’，根据题意，为使割集中的边权值和最小，负数边必选；对于所有正数边，肯定不会选割集之外的边，所以原式就等价于新图中的一个割集，要使原式最小，就要在新图G’种求得一个最小的边割集，所以就将原式的计算转化成了计算新图G’中的最小割。  
然后判断函数就确定了，如果求出的式子 ∑ ( w e − a n s ) ≥ 0 \\sum (w\_e - ans)\\ge 0 ∑(we−ans)≥0，就说明 ∑ e ∈ c w e ∣ c ∣ ≥ a n s \\frac\{\\sum\_\{e\\in c\} w\_e\}\{|c|\}\\ge ans ∣c∣∑e∈cwe≥ans，l = mid 即可。

### 代码详解 ###

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int N = 110,M = 1610,INF = 0x3f3f3f3f;
    const double eps = 1e-8;
    
    int n,m,s,t,dis[N],cur[N];
    int e[M],w[M],ne[M],h[N],idx;	//链式前向星建图
    double f[M];	//边流量是double型
    
    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;	//因为是无向图，正反边流量都存成c
    	ne[idx] = h[b];	
    	h[b] = idx++;
    }
    
    bool bfs()	//dinic模板
    { 
    	queue<int> q;
    	memset(dis,-1,sizeof dis);
    	q.push(s);
    	dis[s] = 0;
    	cur[s] = h[s];
    	while(q.size())
    	{ 
    		int u = q.front();
    		q.pop();
    		for(int i = h[u];~i;i = ne[i])
    		{ 
    			int v = e[i];
     			if(dis[v] == -1 && f[i])
     			{ 
    			dis[v] = dis[u] + 1;
    			cur[v] = h[v];
    			if(v == t)
    			return 1;
    			q.push(v);
    			}
    		}
    	}
    	return 0;
    }
    
    double dfs(int u,double limit)
    { 
    	if(u == t)
    		return limit;
    	double flow = 0;
    	for(int i = cur[u];~i;i = ne[i])
    	{ 
    		cur[u] = i;
    		int v = e[i];
    		if(dis[v] == dis[u]+1 && f[i])
    		{ 
    			double minf = dfs(v,min(f[i],limit-flow));
    			f[i] -= minf;
    			f[i^1] += minf;
    			flow += minf;
    			if(flow == limit)
    				return flow;
    		}
    	}
     return flow;
    }
    
    double dinic()
    { 
    	double ans = 0;
    	while(bfs())
    		ans += dfs(s,INF);
    	return ans;
    }
    
    bool judge(double mid)		//二分的判断函数
    { 
    	double res = 0;
    	for(int i = 0;i < idx;i += 2)
    	{ 
    		if(w[i]-mid <= 0)	//边权值-mid为负数的情况
    		{ 
     			res += w[i]-mid;	//加上负数后总和肯定会减少，所以负数边必选，res记录负数边的总和
    			f[i] = f[i^1] = 0; 	//删除该负数边
    		}
    		else
    			f[i] = f[i^1] = w[i]-mid;	//更新所有边权值减去mid，因为是无向图，正反边都要更新 
    	}
    	return dinic() + res < 0;	//dinic加上res的值就是原式的结果，判断是否小于0
    }
    
    int main()
    { 
    	cin >> n >> m >> s >> t;
    	memset(h,-1,sizeof h);		//初始化链式前向星的头数组
    	while(m--)
    	{ 
    		int a,b,c;
    		cin >> a >> b >> c;
    		add(a,b,c);
    	}
    	double l = 0,r = 1e7;		//二分的左右端点
    	while(r-l > eps)		//因为r、l都是double类型，要加eps防止精度问题产生死循环
    	{ 
    		double mid = (l+r) / 2;
    		if(judge(mid))		//如果原式小于0，则ans应该往小找，r = mid
    			r = mid;
    		else
    			l = mid;	//如果原式大于0，则ans应该往大找
    	}
    	printf("%.2lf\n",r);
    	
    	return 0;
    }

[AcWing2279]: https://www.acwing.com/problem/content/2281/
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/109027273
[01]: https://blog.csdn.net/qq_45735851/article/details/113457900
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/109717899