2016年2月10日 星期三

[Codeforces 223E]Planar Graph

這題乍看之下很棘手,但其實有一個巧妙的解決方法

我們可以先觀察,對於任何一個多邊形,裡面的點和外面的點有甚麼差別?尤其是對邊界的影響
沒錯,從外面的某一點要走到裡面的點要經過奇數次邊界,走到外面的點則是偶數次!
再仔細思考,走到裡面的點進去的次數會比出來的次數多1,走到外面的點則一樣多!

那我們不妨新增一個不管多邊形怎麼給都會在外面的一個點,把這個點連$N$條路徑到每一個點,每當求一個多邊形的答案時,就沿著邊界統計路徑進來多少次、出去多少次,答案就是「進來的次數-出去的次數」
注意考慮的邊應該要是從邊界向外的,否則邊上的點會沒算到

經過同一條邊的路徑可以合併成流量,這樣所有邊的流量可以用一次dfs,$O(N+M)$處理出來

每個點連出去的邊可以先極角排序,再將流量處理成前綴合,這樣沿著邊界統計時每個點的流量才可以$O(1)$算出

至於要統計向外的邊,其實不用執著,只要兩個方向統計出來的答案,取負的那個 (一定有一個$<0$,一個$\geq 0$) 轉正號就好了 (負數的原因是因為流量是向內流進圖形裡面的,而我們統計了向外方向的邊)

時間複雜度:$O(N+M+M\log M+\sum k)$

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
struct Point
{
    LL x,y;
    Point(){}
    Point(const LL &_x,const LL &_y):x(_x),y(_y){} 
    Point operator-(const Point &a)const{return Point(x-a.x,y-a.y);}
    int Quantarium()const
    {
        if(y>=0LL&&x>0LL)return 1;
        if(y>0LL&&x<=0LL)return 2;
        if(y<=0LL&&x<0LL)return 3;
        if(y<0LL&&x>=0LL)return 4;
        assert(!(x==0LL&&y==0LL));
        assert(0);return -1;
    }
    bool operator<(const Point &b)const
    {
        const int qa=Quantarium(),qb=b.Quantarium();
        if(qa!=qb)return qa<qb;
        switch(qa)
        {
            case 1:return y*b.x<b.y*x;//y/x<b.y/b.x
            case 2:return y*(-b.x)>b.y*(-x);//y/-x>b.y/-b.x
            case 3:return (-y)*(-b.x)<(-b.y)*(-x);//-y/-x<-b.y/-b.x
            case 4:return (-y)*b.x>(-b.y)*x;//-y/x>-b.y/b.x
            default:assert(0);return true;
        }
    }
}P[100001];
struct Edge
{
    const int a,b;
    int flow;
    Edge():a(),b(){}
    Edge(const int _a,const int _b,const int _flow):a(_a),b(_b),flow(_flow){}
    bool operator<(const Edge &e)const
    {
        assert(a==e.a);
        return P[b]-P[a]<P[e.b]-P[a];
    }
};
vector<Edge>EDGE;
vector<int>ET[100001],SUM[100000];
map<int,int>IDX[100000];
int Dfs(const int u,bool *vis)
{
    if(vis[u])return 0;
    vis[u]=true;
    int ans=1;
    for(const int ei:ET[u])
    {
        const Edge &e=EDGE[ei];
        const int flow=Dfs(e.b,vis);
        ans+=flow;
        EDGE[ei].flow+=flow,EDGE[ei^1].flow-=flow;
    }
    return ans;
}
int N,M;
void CreateFlow()
{
    static bool vis[100001];
    for(int i=0;i<=N;i++)vis[i]=false;
    assert(Dfs(N,vis)==N+1);
}
void AddEdge(const int a,const int b)
{
    const int sz=EDGE.size();
    EDGE.push_back(Edge(a,b,0));
    ET[a].push_back(sz);
}
int GetSum(const int a,const int o,const int b,const bool type)
{
    const vector<int>&sum=SUM[o];
    const auto ita=IDX[o].find(a),itb=IDX[o].find(b);
    assert(ita!=IDX[o].end()&&itb!=IDX[o].end());
    const int ia=(type?itb:ita)->second;
    const int ib=(type?ita:itb)->second;
    assert(ia!=ib);
    if(ia<ib)return sum[ib-1]-sum[ia];
    else return sum[(int)sum.size()-1]-(sum[ia]-(ib?sum[ib-1]:0));
}
bool CmpEdgeIdx(const int a,const int b){if(a==b)return false;return EDGE[a]<EDGE[b];}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<=N;i++)ET[i].clear();
        EDGE.clear();
        for(int i=0,a,b;i<M;i++)
        {
            scanf("%d%d",&a,&b),a--,b--;
            AddEdge(a,b),AddEdge(b,a);
        }
        for(int i=0;i<N;i++)scanf("%I64d%I64d",&P[i].x,&P[i].y);
        if(true)
        {
            LL mn=INF;
            int left=-1;
            for(int i=0;i<N;i++)if(P[i].x<mn)mn=P[i].x,left=i;
            assert(left!=-1);
            AddEdge(left,N),AddEdge(N,left);
            P[N].x=-1e9-1,P[N].y=P[left].y;
        }
        CreateFlow();
        for(int i=0;i<N;i++)
        {
            sort(ET[i].begin(),ET[i].end(),CmpEdgeIdx);
            IDX[i].clear();
            for(int j=0;j<(int)ET[i].size();j++)IDX[i][EDGE[ET[i][j]].b]=j;
            SUM[i].clear();
            int sum=0;
            for(const int ei:ET[i])SUM[i].push_back(sum+=EDGE[ei].flow);
            assert(IDX[i].size()==ET[i].size()&&SUM[i].size()==ET[i].size());
        }
        int querycount;scanf("%d",&querycount);
        for(int k;querycount--;)
        {
            scanf("%d",&k);
            vector<int>a;
            for(int i=0,v;i<k;i++)scanf("%d",&v),a.push_back(--v);
            assert(k==(int)a.size()&&k>=3);
            int ans1=0,ans2=0;
            for(int i=0;i<k;i++)
            {
                ans1+=GetSum(a[i],a[(i+1)%k],a[(i+2)%k],false);
                ans2+=GetSum(a[i],a[(i+1)%k],a[(i+2)%k],true);
            }
            printf("%d\n",-min(ans1,ans2));
        }
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原