Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

NEERC 2006 Hard Life

题意:
给定一个图(V<=100,E<=1000) 求一个子图(V',E') 使得|E'| 与 |V'|的比值最大,要求出这个子集。

做法:
比较裸的最大密度子图。
设密度为R 要令R最大
R=max{|E'|/|'V'|} 化简得到 max{|E'|-R*|'V'|}=0
设 g(x)=max{|E'|-x*|'V'|}
由Dinkelbach定理与该函数的单调性得到:
                  g(x)=0  当且仅当 x=R
                  g(x)<0  x>R
                  g(x)>0  x<R

所以可以利用二分答案 二分R  (下界为1/N 上界为M)
接下来就变成了如何验证x是否符合。

将式子进行转化 取g(x)<0为例
两边取负得到 min{x*|V'|-|E'|}>0
同时加上|E|得到  min{(|E|-|E'|)+x*|V'|}>E
将式子解读一下可以知道  要我们求的是 未选的边与选中的点数乘x的和是否大于E
左边的式子很熟悉
|E|中的每一条边依附于|V|中的点 同时要使选出来的点总数*x加上选出来的边数最小
这便是一个最大权闭合图的问题。

我们设立源S  汇T
从S向所有的点连权值为x的边
对于每条边e=(u,v) u,v各向e连一条无穷的边
从所有e向T连容量为1的边 求出最大流
g(x)即求得

对于求方案 由最小割的定义 我们bfs一遍 求出从S可以到达的所有点 这是S集合
另外点属于T集合。对于所有跨越S-T的边便是割边。

求点的方案等价于求出有一个端点为S的所有割边  另一个端点便是选的所有点

注意点:
本题对于精度要求很奇怪  全设作1e-7 自己电脑上跑不过 pku上能过..好吧我的g++版本太低了

  1#include <cstdio>
  2#include <cstring>
  3#define min(a,b) ((a)<(b)?(a):(b))
  4#define oo 1e10
  5#define eps 1e-7
  6#define n 2005
  7#define m 20005
  8
  9int vtx[m],ne[m],tot;
 10int d[n],L[n],q[n],pre[n],x[n],y[n],S,T,now,N,M,ret;
 11double f[m],Mincut;
 12bool mk[n],vis[n],cut[m];
 13
 14inline void Ins(int u,int v,double fl)
 15{
 16    vtx[++tot]=v;f[tot]=fl;ne[tot]=L[u];L[u]=tot;
 17    vtx[++tot]=u;f[tot]=0;ne[tot]=L[v];L[v]=tot;
 18}

 19inline void push()
 20{
 21    double fl=oo;
 22    for (int i=T;i!=S;i=vtx[pre[i]^1])
 23        fl=min(fl,f[pre[i]]);
 24    Mincut+=fl;
 25    for (int i=T;i!=S;i=vtx[pre[i]^1])
 26    {
 27        f[pre[i]]-=fl,f[pre[i]^1]+=fl;
 28        if (f[pre[i]]<eps)    now=vtx[pre[i]^1];
 29    }

 30}

 31inline void dinic(int u)
 32{
 33    if (u==T)    push();
 34    else
 35    {
 36        for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
 37        if (f[p]>eps&&d[u]+1==d[v])
 38        {
 39            pre[v]=p,dinic(v);
 40            if (d[now]<d[u])    return;
 41            now=T;
 42        }

 43        d[u]=-1;
 44    }

 45}

 46inline bool extend()
 47{
 48    memset(d,63,sizeof(d));
 49    d[q[1]=S]=0;
 50    for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
 51    for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
 52    if (f[p]>eps&&d[v]>(1<<29))
 53    {
 54        d[v]=d[u]+1;
 55        if (v==T)    return 1;
 56        q[++t]=v;
 57    }

 58    return 0;
 59}

 60inline double check(double g)
 61{
 62    memset(L,0,sizeof(L));
 63    tot=1;
 64    for (int i=1;i<=N;++i)
 65        Ins(S,i,g);
 66    for (int i=1;i<=M;++i)
 67        Ins(x[i],N+i,oo),Ins(y[i],N+i,oo),Ins(N+i,T,1);
 68    for (Mincut=0;extend();dinic(S));
 69    return Mincut<M;
 70}

 71inline void findcut()
 72{
 73    vis[q[1]=S]=1;
 74    for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
 75    for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
 76    if (f[p]>1e-4&&!vis[v])    vis[q[++t]=v]=1;
 77    for (int u=1;u<=T;++u)
 78    for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
 79    if (!(p&1)&&(vis[u]^vis[v]))    cut[p]=1;
 80}

 81int main()
 82{
 83    scanf("%d%d",&N,&M);
 84    if (!M)    return printf("1\n1\n"),0;
 85    for (int i=1;i<=M;++i)
 86        scanf("%d%d",&x[i],&y[i]);
 87    S=N+M+1,T=S+1;
 88    int Time=24;
 89    double l=1/N,r=M,mid;
 90    for (mid=(l+r)/2;Time--;mid=(l+r)/2)
 91    if (check(mid))    l=mid;
 92    else    r=mid;
 93    check(l),findcut();
 94    for (int p=L[S],v=vtx[p];p;v=vtx[p=ne[p]])
 95    if (cut[p])    ++ret,mk[v]=1;
 96    printf("%d\n",ret);
 97    for (int i=1;i<=N;++i)
 98    if (mk[i])    printf("%d\n",i);
 99    return 0;
100}

101

posted on 2010-04-16 16:29 jsn1993 阅读(633) 评论(0)  编辑 收藏 引用 所属分类: Graph Theory && Network Flow


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理