设为首页 加入收藏

TOP

计算几何 图论 网络流思想(三)
2012-11-04 13:52:18 来源: 作者: 【 】 浏览:854
Tags:计算 几何   图论 网络 思想

 

    if(!vis[v]) cnt+=dfs(v,u);

    }

    if(f)

    {

    flow[MP(f,u)]+=cnt;

    flow[MP(u,f)]-=cnt;

    }

    return cnt;

    }

    int ss[maxn],tt[maxn];

    vector<int> cut;

    inline int gao(int a,int b,int c)

    {

    double bb = p[b]/p[a],cc = p[c]/p[a];

    if(bb < cc)

    {

    return sum[MP(a,c)] - sum[MP(a,b)] - flow[MP(a,c)];

    }

    else

    {

    return all[a] + sum[MP(a,c)] - sum[MP(a,b)] - flow[MP(a,c)];

    }

    }

    void solve()

    {

    int ans=0,num=cut.size(),i;

    double s=0;p[0]=Point(0,0);

    for(i=0;i<num;i++)

    s+=chacha(p[0],p[cut[i==0 num-1 : i-1]],p[cut[i]]);

    if(s>0) reverse(cut.begin(),cut.end());//变成顺时针

    for(i=0;i<num;i++)

    {

    int tmp=gao( cut[i], cut[(i==0 num-1 : i-1)] , cut[(i+1)%num] ) ;

    ans+=tmp;

    }

    printf("%d\n",ans+num);

    }

    int main()

    {

    int u,v,q,k,i,j,leftmost,T,cir,c;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)  scanf("%d%d",&ss[i],&tt[i]);

    for(i=1;i<=n;i++)  scanf("%lf%lf",&p[i].x,&p[i].y);

    for(i=1;i<=m;i++)

    {

    add_edge(ss[i],tt[i]);

    add_edge(tt[i],ss[i]);

    }

    p[T=n+1]=Point(-inf,0);

    for(leftmost=i=1;i<=n;i++)

    if(p[i]<p[leftmost])   leftmost=i;

    add_edge(T,leftmost);

    add_edge(leftmost,T);

    dfs(T,0);

    for(i=1;i<=n+1;i++) sort(edge[i].begin(),edge[i].end());

    for(i=1;i<=n+1;i++)

    {

    int pre=i;

    sum[MP(i,i)] = 0;

    for(vector<Edge>::iterator it=edge[i].begin();it!=edge[i].end();it++)

    {

    all[i]+=flow[MP(i,it->to)];

    sum[MP(i,it->to)] = sum[MP(i,pre)] + flow[MP(i,it->to)];

    pre=it->to;

    }

    }

    scanf("%d",&q);

    while(q--)

    {

    scanf("%d",&k);cut.clear();

    for(i=1;i<=k;i++) scanf("%d",&c),cut.PB(c);

    solve();

    }

    return 0;

    }

      

首页 上一页 1 2 3 4 下一页 尾页 3/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇搜狐2012校园招聘会笔试题 下一篇ActiveX技术综述

评论

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