[POJ 3155] 最大密度子图、最大权闭合图、分数规划、求最小割

【题目大意】求一个无向图的最大密度子图

【算法分析】

这里有论文http://u.115.com/file/f7142414ae 最小割.pdf

我是直接套最大权闭合图来做的。

首先

密度P=Ex / Vy

0=Ex / Vy – P

令H=Ex / Vy – P

则两边同乘Vy得:H * Vy = Ex – P * Vy

由于该式满足单调性,于是我们可以二分P,使得H=0时,就可以取得P的确切值。

而式子右边则是最大权闭合图的计算定义,于是我们可以直接套用最大权闭合图求解。

【HINT】注意精度和H最后必须>0,否则你求得的是没有任何一个点,因为H=0时最大权闭合图的方案应该是一个点也不取,只要让它稍微>0,就可以利用割找到取了哪些点了。

【其它】交了34次,做了1个月,终于AC

【程序】

#include #include #define eps 1e-9
#define eps2 1e-6
#define INF 1e20
#define N 100000
using namespace std;
struct gtp{int x,y,next,op;double c;}g[N];
int n,m,e,ls[N],d[N],fa[N],cur[N],num[N],mark[N],edge[N][2],S,T,ans=0;

void init(){
    for (int i=1;i<=m;i++)
      scanf("%d%d",&edge[i][0],&edge[i][1]);
}   

void relabel(int k){
    int mm=T;
    cur[k]=ls[k];
    for (int t=ls[k];t!=0;t=g[t].next)
      if (g[t].c>0) mm=min(mm,d[g[t].y]);
    d[k]=mm+1;
}

double change(){
    double flow=INF;
    for (int i=T;i!=S;i=g[fa[i]].x) flow=min(flow,g[fa[i]].c);
    for (int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c-=flow;
        g[g[fa[i]].op].c+=flow;
    }   
    return flow;
}   

double sap(){
    double flow=0;
    for (int i=S;i<=T;i++){
        d[i]=0;
        cur[i]=ls[i];
        num[i]=0;
    }   
    num[0]=T+1;
    int i=S;
    while (d[S]        while (cur[i]!=0)
          if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
          else cur[i]=g[cur[i]].next;
        if (cur[i]==0){
            if (–num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=S) i=g[fa[i]].x;
        }
        else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==T){
                flow+=change();
                i=S;
            }   
        }       
    }   
    return flow;
}   

void addedge(int x,int y,double c){
    e++;
    g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
    e++;
    g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}   

double check(double limit){
    e=0; S=0; T=n+m+1;
    memset(ls,0,sizeof(int)*(T+1));
    for (int i=1;i<=n;i++) addedge(i,T,limit);
    for (int i=1;i<=m;i++){
        addedge(S,n+i,1.0);
        addedge(n+i,edge[i][0],INF);
        addedge(n+i,edge[i][1],INF);
    }   
    return m-sap();
}   

void dfs(int k){
    mark[k]=1;
    if (k>0 && k<=n) ans++;
    for (int t=ls[k];t!=0;t=g[t].next)
      if (g[t].c>0 && mark[g[t].y]==0)
        dfs(g[t].y);
}   

void solve(){
    if (m==0){
        printf("1n1n");
        return;
    }   
    init();
    double l=0,r=m,mid,ret;
    while (l+eps        mid=(l+r)/2;
        ret=check(mid);
        if (fabs(ret)            bool flag=false;
            for (int t=ls[0];t!=0;t=g[t].next)
              if (g[t].c>0){
                  flag=true;
                  break;
              }   
            if (flag) break;
            r=mid-eps;
        }   
        else l=mid+eps;
    }   
    memset(mark,0,sizeof(int)*(T+1));
    ans=0;
    dfs(S);
    printf("%dn",ans);
    for (int i=1;i<=n;i++)
      if (mark[i]==1) printf("%dn",i);
}   

int main(){
    while (scanf("%d%d",&n,&m)!=EOF) solve();
    return 0;
}   

留下评论

您的电子邮箱地址不会被公开。