分数规划问题

以前我都叫它二分的。
反正模型往往显然。
今天hentai的dashgua给我们普及了一些专有名词。如果是普及向的话还是戳他的链接吧。
额。还普及了一个类似迭代法求最优解的算法。

noip复习一下咯。。。

1.USACO Jan07 考试

cstdio的题解很赞。注意到把问题规约到求略去的里面最大的一个和被选择的里面最小的一个进行比较即可。
然后两个子问题都是凸包中的经典问题。强上数据结构自然是兹瓷的。但是题解中似乎讲述了什么不可思议的推理技巧。

感觉我写的好丑。

typedef pair<int,int> poi;

const int MAXN = 5E4+10;

poi p[MAXN]; 
int id[MAXN];

int sta[MAXN];

double G[MAXN];
double best[MAXN];
double worst[MAXN];

int n;

bool cmp(int a,int b)
{
    return p[a].sc*p[b].fr<p[b].sc*p[a].fr;
}

void init()
{
    RI(n);
    REP(i,1,n) RII(p[i].sc,p[i].fr),id[i]=i;
    sort(id+1,id+1+n,cmp);
    int A=0,B=0,ii;
    REPD(i,n,1)
    {
        ii=id[i];
        A+=p[ii].sc;
        B+=p[ii].fr;
        G[i]=A*1.0/B;
    }
}

void getbest()
{
    int top=0;
    int ii;
    REP(i,1,n-1)
    {
        ii=id[i];
        while (top && p[sta[top]].fr>p[ii].fr) top--;
        while (top>1 && (p[ii].sc-p[sta[top-1]].sc)*(p[sta[top]].fr-p[sta[top-1]].fr) > (p[sta[top]].sc-p[sta[top-1]].sc)*(p[ii].fr-p[sta[top-1]].fr) ) top--;
        
        sta[++top]=ii;
        
        while(top>1 && (p[sta[top]].sc-G[i+1]*p[sta[top]].fr)<(p[sta[top-1]].sc-G[i+1]*p[sta[top-1]].fr) ) top--; 

        best[i]=p[sta[top]].sc-G[i+1]*p[sta[top]].fr;
    }
}

void getworst()
{
    int top=0;
    int ii;
    REPD(i,n,2)
    {
        ii=id[i];
        while (top && p[sta[top]].fr<p[ii].fr) top--;
        while (top>1 && (p[sta[top-1]].sc-p[ii].sc)*(p[sta[top-1]].fr-p[sta[top]].fr)>(p[sta[top-1]].sc-p[sta[top]].sc)*(p[sta[top-1]].fr-p[ii].fr) ) top--;

        sta[++top]=ii;

        while (top>1 && (p[sta[top-1]].sc-G[i]*p[sta[top-1]].fr)<(p[sta[top]].sc-G[i]*p[sta[top]].fr) ) top--;
        worst[i]=p[sta[top]].sc-G[i]*p[sta[top]].fr;
    }
}

int main()
{
    open();
    int _=0;
    init();
    getbest();
    getworst();
    int ans=0;
    REP(i,1,n-1)
        ans+=best[i]>worst[i+1];
    printf("%d\n",ans);
    REP(i,1,n-1)
        if (best[i]>worst[i+1])
            printf("%d\n",i);
    close();
    return 0;
}

2.一类可以用网络流解决的分数规划问题
Amber论文:最大权闭合图&&最大密度子图
ZOJ2676 最优比率最小割
开始以为是什么高的不得了的东西。看见题我就笑了。
一样的思路。二分。然后判定是否存在解。
不过发现一些细节。权值小于0的边直接入最小割。(在原图中把它割断就好)。然后其余边继续最小割。
思考熊。实数最大流真的大丈夫?
注意原题是双向边。多组数据,中间换行。

void bfs()
{
    MS(belong,0);
    int l=0,r=0;
    int now;
    que[r++]=n;
    belong[n]=1;
    while (l!=r)
    {
        now=que[l++];
        for (int i=hd[now];i!=-1;i=nxt[i])
            if (!belong[to[i]] && f[i^1]>0)
                que[r++]=to[i],belong[to[i]]=1;
    }
}

vector<int> ans;

void work()
{
    double mid=0;
    while (R-L>eps)
    {
        mid=(L+R)/2;
        if (chk(mid)) L=mid;
        else R=mid;
    }
    MS(f,0);
    REP(i,1,m)
        if (val[i]>R)
            f[(i-1) << 1]=f[((i-1) << 1)|1]=val[i]-R;
    while (SPFA()) dfs(1,1e20);
    bfs();
    ans.clear();
    
    REP(i,1,m)
        if (val[i]<=R)
            ans.pb(i);
        else if ((belong[to[(i-1) << 1]]^belong[to[((i-1) << 1)|1]])==1)
            ans.pb(i);

    printf("%d\n",ans.size());
    printf("%d",ans[0]);
    REP(i,1,ans.size()-1)
        printf(" %d",ans[i]);
    printf("\n");
}

poj 3155
最大密度子图。前置技能最大权闭合图(考虑哪些点不被选分正负权值转化成最小割模型)
1.确定二分定界。注意到密度差不小于(作差即可证明)
2.考虑选一个密度最大的子图一定是选了这条边就一定选了这条边的两个端点。转为最大权闭合图。
3.= =b 居然又是实数网络流。
4.坑。。开始想先用simple Algorithm写一发练练手。
结果发现,这个算法只适用于求出最大密度,并不能正确的输出方案。(WA了一晚上

UPD:2015.10.25

5.只好写了一发改进算法。证明还蛮容易的。注意一些精度问题。这里也给一些小测资。discuss里面的也相当兹瓷,建议看看。

input
5 2
1 2
5 4

output
4
1
2
4 
5

另。发一份test到网盘去,交出神秘链接

因为时间永远分岔,通向无数的未来。

double h(double k){
    double ret=m*n;
    int U=m;
    MS(hd,-1);
    tot=-1;
    MS(f,0);
    src=0;
    snk=n+1;
    REP(i,1,n)
        add(src,i,U),
        add(i,src,0);
    REP(i,1,m)
        add(E[i].fr,E[i].sc,1),
        add(E[i].sc,E[i].fr,1);
    REP(i,1,n)
        add(i,snk,2*k-id[i]+U),
        add(snk,i,0);
    ret=ret-dinic();
    return ret/2;
}

vector<int> ans;

void dfs(int p)
{
    cut[p]=1;
    for (int i=hd[p];i!=-1;i=nxt[i])
        if (dcmp(f[i])>0 && !cut[to[i]])
            dfs(to[i]);
}

void work()
{
    double L=1.0/n,R=m;
    double mid;
    while (R-L>1.0/n/n)
    {
        mid=(L+R)/2;
        if (dcmp(h(mid))>0)
            L=mid;
        else 
            R=mid;
    }
    h(min(L,R));
    dfs(src);

    REP(i,1,n)
        if (cut[i])
            ans.pb(i);
    printf("%d\n",ans.size());
    REP(i,0,ans.size()-1)
        printf("%d\n",ans[i]);
}

上述问题是边点均为带上权值的。
我们思考带上边权的时候,把1换成边权,把度数换成相邻的边权和。
考虑点权的话。那么原来的变成了相应的我们调整U

UPD:2015.10.28

3.重建计划

我是ドM...是的你应该相信这一点..为了身体健康这道题,我应该学习吴翼大爷写三遍。
a.点分治+线段树+二分
b.树链剖分+平衡树
c.特殊的技巧各种卡常卡卡卡卡,或者学习吴翼大爷写凸包。或者学习byvoid写单调队列。
然而。吴翼大爷的7份std(都是自己写的,每一份都是一个算法!)然而只有一个能A咯..
不管了。作为一个ドM还是要推荐我的写法。。
存分治结构的点分治+迭代+线段树还是很excited的!感觉特别爽!
这些卡常技巧都是莫涛和吴翼写过的。。翱犇也在blog有所记录。
Because of this problem ,I put off all my tasks.

4.配合单调队列使用。BZOJ3316
DZY出的好题。

Recent Posts

comments powered by Disqus