设为首页 加入收藏

TOP

poj 3155 Hard Life(最大密度子图，01分数规划)
2015-07-24 07:12:19 来源: 作者: 【大 中 小】 浏览:61次
Tags：poj 3155 Hard Life 最大 密度 01分数 规划

?

?

大致题意：给出一个无向图，求出它的一个最大密度子图，最大密度子图定义为子图的边数与顶点数的比值。

?

详见amber论文中关于最大密度子图

本题要注意的地方：

当m为0时也要输出内容。

二分的边界是 1/n/n(high - low >1/n/n) ,这在amber论文引理4.1中有讲解

因为h函数的特性，恒有h >=0，即h函数不是一个严格递减的函数，当减小到0时便不再减小。那么我们要取得的是第一个为0的，所以要二分下界，而不是直接取mid,因为没有意识到函数特性，WA了N次。

二分完毕后，并不能求出正确的low值，ms也是因为该函数的特性，我们还要再求一遍最大流。

根据残量网络求最大密度子图：从源点dfs,走残量网络中流量大于0的边并标记。

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define LL long long #define _LL __int64 #define eps 1e-8 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 110; const int maxm = 1010; struct node { int u,v; double w; int next,rev; }p[maxm],edge[maxm*6]; int s,t,n,m,nn; int cnt,head[maxn]; int d[maxn]; int dist[maxn],vis[maxn]; int ans; void init() { cnt = 0; memset(head,-1,sizeof(head)); } void add(int u, int v, double w) { edge[cnt] = (struct node){u,v,w,head[u],cnt+1}; head[u] = cnt++; edge[cnt] = (struct node){v,u,0,head[v],cnt-1}; head[v] = cnt++; } void build(double mid) { init(); for(int i = 1; i <= m; i++) { add(p[i].u,p[i].v,1.0); add(p[i].v,p[i].u,1.0); } for(int i = 1; i <= nn; i++) { add(s,i,m); add(i,t,m*1.0+2*mid-d[i]*1.0); } } bool bfs() { queue 
            
              que; memset(dist, 0, sizeof(dist)); memset(vis, 0, sizeof(vis)); while(!que.empty()) que.pop(); vis[s] = 1; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].w && !vis[v]) { que.push(v); vis[v] = 1; dist[v] = dist[u]+1; } } } if(dist[t] == 0) return false; return true; } double dfs(int u, double delta) { if(u == t) return delta; double ret = 0,tmp; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].w && dist[edge[i].v] == dist[u]+1 && (tmp = dfs(v,min(delta,edge[i].w)))) { edge[i].w -= tmp; edge[edge[i].rev].w += tmp; return tmp; } } if(!ret) dist[u] = -1; return ret; } double Dinic() { double ans = 0,res; while(bfs()) { while(res = dfs(s,INF)) ans += res; } return ans; } void dfs_cut(int u) { vis[u] = 1; if(u <= nn) ans++; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].w > 0 && !vis[v]) { dfs_cut(v); } } } int main() { while(~scanf(%d %d,&n,&m)) { if(m == 0) { printf(1 1 ); continue; } memset(d,0,sizeof(d)); for(int i = 1; i <= m; i++) { scanf(%d %d,&p[i].u,&p[i].v); d[p[i].u]++; d[p[i].v]++; } s = n+1; t = n+2; nn = n; n = t; double low,high,mid,h; low = 0.0; high = m; while(high - low > 1.0/nn/nn) { mid = (high + low)/2; build(mid); h = (m*nn*1.0 - Dinic() )/2; if(h > eps) low = mid; else high = mid; } build(low); Dinic(); ans = 0; memset(vis,0,sizeof(vis)); dfs_cut(s); printf(%d ,ans); for(int i = 1; i <= nn; i++) { if(vis[i]) printf(%d ,i); } } return 0; }


?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：最短路径-zoj-2797 下一篇：WPF{ComboBox绑定类对象， 下拉列..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: