本文主要是介绍poj3155--Hard Life（最大密度子图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj3155:题目链接
题目大意：给出了n个点，m条无向边，选一个集合M，要求集合中的边数/点数的最最大
参考：最小割模型在信息学竞赛中的应用
先做了0-1分数规划，然后最大权闭合图，然后是最大密度子图。最大密度子图要用到前两个知识点。
注意：精度问题，这个题的单调性会出现一段为0的值，所以要用二分逼近最左侧的那个，然后在二分完成后，要用low(左边界)再求一次，这样是最精确的
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define eqs 1e-12
using namespace std ;
struct node{int u , v ;double w ;int next ;
}edge[10000] , p[1200] ;
int head[120] , cnt ;
int l[120] , n , m , con[120] ;
int vis[120] , num ;
queue <int> que ;
void add(int u,int v,double w) {edge[cnt].u = u ; edge[cnt].v = v ; edge[cnt].w = w ;edge[cnt].next = head[u] ; head[u] = cnt++ ;edge[cnt].u = v ; edge[cnt].v = u ; edge[cnt].w = 0 ;edge[cnt].next = head[v] ; head[v] = cnt++ ;
}
int bfs(int s,int t) {int u , v , i ;memset(l,-1,sizeof(l)) ;l[s] = 0 ;while( !que.empty() ) que.pop() ;que.push(s) ;while( !que.empty() ) {u = que.front() ;que.pop() ;for(i = head[u] ; i != -1; i = edge[i].next) {v = edge[i].v ;if( l[v] == -1 && edge[i].w >= eqs ) {l[v] = l[u] + 1 ;que.push(v) ;}}}if( l[t] > 0 ) return 1 ;return 0 ;
}
double dfs(int s,int t,double min1) {if(s == t) return min1 ;int i , v ;double a , ans = 0 ;for(i = head[s] ; i != -1 ; i = edge[i].next) {v = edge[i].v ;if( l[v] == l[s]+1 && edge[i].w >= eqs && ( a = dfs(v,t,min(min1,edge[i].w) ) ) ) {edge[i].w -= a ;edge[i^1].w += a ;ans += a ;min1 -= a ;if( min1 < eqs ) break ;}}if( ans >= eqs ) return ans ;l[s] = -1 ;return 0 ;
}
double solve(double g) {memset(head,-1,sizeof(head)) ;cnt = 0 ;int i , j ;double temp , max_flow = 0 ;for(i = 0 ; i < m ; i++) {add(p[i].u,p[i].v,1.0) ;add(p[i].v,p[i].u,1.0) ;}for(i = 1 ; i <= n ; i++) {add(n+1,i,m) ;add(i,n+2,m+2*g-con[i]) ;}while( bfs(n+1,n+2) ) {while( ( temp = dfs(n+1,n+2,m) ) >= eqs ) {max_flow += temp ;}}return ((double)m*n-max_flow)/2.0 ;
}
void f_dfs(int u) {int i , v ;for(i = head[u] ; i != -1 ; i = edge[i].next) {v = edge[i].v ;if( !vis[v] && edge[i].w >= eqs ) {vis[v] = 1 ;num++ ;f_dfs(v) ;}}
}
int main() {int i , j ;int u , v ;double low , high , mid , temp ;while( scanf("%d %d", &n, &m) != EOF ) {if( m == 0 ) {printf("1\n1\n") ;continue ;}memset(con,0,sizeof(con)) ;memset(head,-1,sizeof(head)) ;cnt = 0 ;for(i = 0 ; i < m ; i++) {scanf("%d %d", &p[i].u, &p[i].v) ;con[ p[i].u ]++ ;con[ p[i].v ]++ ;}low = 0 ; high = m ;while( high - low >= 1e-5 ) {mid = (low+high)/2.0 ;temp = solve(mid) ;if( temp >= eqs )low = mid ;elsehigh = mid ;}temp = solve(low) ;num = 0 ;memset(vis,0,sizeof(vis)) ;vis[n+1] = 1 ;f_dfs(n+1) ;printf("%d\n", num) ;for(i = 1 ; i <= n ; i++) {if( !vis[i] ) continue ;printf("%d\n", i ) ;}}return 0 ;
}
这篇关于poj3155--Hard Life（最大密度子图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
