本文共 1705 字，大约阅读时间需要 5 分钟。

题意

给定一个无向图,求一个子图,最大化$\frac{E}{V}$

其中$E$表示边数,$V$表示点数

考虑01分数规划

$f(r)=E-V\ast r$

对于不同的子图选择,对应的直线也不尽相同

但斜率始终为负数

所以二分$r$,作直线$x=r$交于若干个点

若存在某个交点$y$座标大于零,说明还在右边

所以需要求出最大值来判断

最大值怎么求,考虑网络流。

选择一个点获得$-r$的权值,选择一条边获得$1$的权值

但边的选择依赖于两个点的选择

所以就是一个最大权闭合子图

比较巧妙,把边也当成物品就好了

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn=2e5+10;const int inf = 1e9+10;const double eps=1e-6;struct edge{
   	int to,nxt; double flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double flow){
   	d[++cnt] = (edge){
   v,head[u],flow},head[u]=cnt;	d[++cnt] = (edge){
   u,head[v],0},head[v]=cnt;}int n,m,s,t,dis[maxn],u[maxn],v[maxn];bool bfs(){
   	queue
      
       q;	for(int i=0;i<=t;i++)	dis[i]=0;	q.push(s); dis[s]=1;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v=d[i].to;			if( dis[v]==0&&d[i].flow>eps )				{
   				dis[v]=dis[u]+1;				if( v==t )	return true;				q.push(v);			}		}	}	return false;}double dinic(int u,double flow){
   	if( u==t )	return flow;	double res=flow;	for(int i=head[u];i&&res>eps;i=d[i].nxt )	{
   		int v = d[i].to;		if( d[i].flow>eps && dis[v]==dis[u]+1 )		{
   			double temp = dinic(v,min(res,d[i].flow));			if( temp
       
        > n >> m )	{
   		if( m==0 )		{
   			cout << 1 << "\n" << 1 << endl;			continue;		}		for(int i=1;i<=m;i++)	cin >> u[i] >> v[i];		double l = 0,r = m,ans = 0;		while( r>l+1e-5 )		{
   			double mid = (l+r)/2.0;			if( isok(mid)>eps )	l=mid,ans=mid;			else	r=mid;		}		isok(ans); bfs();		vector
        
         vec; for(int i=1;i<=n;i++) if( dis[i] ) vec.push_back(i); cout << vec.size() << '\n'; for(int i=0;i
        
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109356497 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！