2015年5月31日 星期日

[CF 547D] Mike and Fish

這題感覺我的作法爛爛的,建議先理解官方解還有dreamoon的code,都寫的蠻清楚的@@

作法:

首先考慮一個會有問題的作法:對於每個點,往他上下左右四個方向最近的點分別連一條邊(如果沒有點就不用連),然後直接對這張圖二塗色。而這樣隨便都能構一個出現奇環的測資讓他爛掉,因此我們可以考慮先把圈都拔光,具體來說,我們考慮一種比較特別的圈,如果沿著這樣的圈一直走的話,走的方向依序是「橫直橫直......」,也就是每走一個點都會轉$90$度。顯然這樣的圈的點數為偶數,那麼沿著這個圈一路途上紅藍交錯的顏色,就可以把這個圈上的所有點砍掉了,因為塗完後他讓每條鉛直線和水平線上的紅藍點數增加的個數相同。因此只要把這種圈都砍完之後,剩下的圖就可以用剛才提到的那個演算法了:直接把圖建出來二塗色,因為此時已經沒有圈了(容易證明,當不存在剛才那種「特別的圈」時,原本的圖裡也不會有圈),所以直接塗就可以了。

所以重點在於要如何找圈然後把他拔掉,首先考慮直接DFS的算法,也就是走到一個點的時候,考慮所有和他同行(或同列,只會是其中一個,因為我們要找的是剛才提到的特別的圈)的點DFS下去,當找到一條回邊,也就是形成了一個圈時,就沿著父親一直走上去,並沿路塗色,塗完後直接中斷這次的DFS,一直 return 回去直到當前的點的答案還沒被決定為止,然後之後在DFS的時候就可以完全無視那些已經被塗過色的點了。這個算法還有需要注意的地方,因為當我們最一開始DFS的時候一定是先選一個方向去DFS,也就是假設從這個點出發是先走橫的,這樣之後DFS的過程就知道現在這個點的下一步是走橫的還是直的。而如果結束DFS的時候根節點還沒有被塗色,就要去DFS起點是走直的的情況,否則之後在以其他點當根DFS的時候,當戳到了這個還沒被塗色的舊根節點時會誤以為這是一條回邊,這時沿著父親走就會爛掉。

顯然這個算法複雜度會爛掉,於是我只好用 linked list 優化 DFS ,這東西在TIOJ 1220也有用到類似的東西(雖然我當時的解不是那樣做的),具體來說就是:對每個$x$座標維護一條 linked list ,代表當前的$x$座標等於他的點中還剩下這些點。對每個$y$座標一樣也有一條 linked list 。由這裡可以看出每個原圖中的點$P$會對應到兩個在 linked list 中的節點$nx,ny$(其中$nx$是被放在「$x$座標的lonked list」中的節點,$ny$則是$y$座標的),並且讓$nx$代表走到$P$時下一步是要走鉛直方向的,$ny$則是代表走到$P$時下一步是要走水平方向的。

建好 linked list 後就可以DFS了,當走到一個點$P$時,假設他現在要走的是直的方向,那麼就先把他對應的$nx$拔掉,然後去他的$x$座標這條 linked list 裡找後繼節點,當找到一個後繼節點$Q$時就直接把$Q$對應的$nx$拔掉再DFS下去,一樣當找到一個圈的時候就一樣沿路塗色並一直 return 。但這樣做會有問題,會發現根本找不到圈,因為當一個點被走到時他所對應的$nx,ny$都已經被拔掉了,之後當然就不會有任何邊走向他了。解決方法是當在DFS時,假設現在是$P$找到了他的後繼節點$Q$(和剛剛一樣),那麼在DFS下去之前先不要把$Q$的$nx$拔掉,等到DFS出來之後再拔掉,因為如果有圈形成的話他的回邊一定是連向$Q$的$nx$的。最後還要注意到剛才用 linked list 優化之前的那個細節,也就是根節點要記得擴展完,因此當最一開始DFS進去是選$x$方向的 linked list 的話,出來之後發現根節點還沒被塗色,就要試試看選$y$方向的。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
struct P{int x,y,id;};
bool cmp1(const P &a,const P &b)
{
    return a.x==b.x ? a.y<b.y : a.x<b.x ;
}
bool cmp2(const P &a,const P &b)
{
    return a.y==b.y ? a.x<b.x : a.y<b.y ;
}
 
P p[maxn] ;
 
struct node
{
    node *las,*nex ;
    int id ;
    node(int _id){las=nex=NULL ; id=_id ;}
}*head[3][maxn] , *nd[3][maxn] ;
 
void add_node(int type,int x,int id)
{
    node *u=head[type][x] ;
    head[type][x]=new node(id) ;
    head[type][x]->nex=u ;
    if(u) u->las=head[type][x] ;
}
 
void erase(int type,int id,node *u)
{
    if(u==head[type][id]) head[type][id]=u->nex ;
    else
    {
        u->las->nex=u->nex ;
        if(u->nex) u->nex->las=u->las ;
    }
}
 
bool vis[maxn] ;
int fa[maxn],ans[maxn] ;
void dfs(int x,int f,int type)
{
    vis[x]=1 ; fa[x]=f ;
    int id=(type==1 ? p[x].x : p[x].y) ;
    erase(type,id,nd[type][x]) ;
 
    for(node *u=head[type][id];u;u=head[type][id])
    {
        if(vis[u->id])
        {
            for(int i=x,col=type^3;;i=fa[i],col^=3)
            {
                ans[i]=col ;
                int id2=(col==1 ? p[i].x : p[i].y) ;
                erase(col,id2,nd[col][i]) ;
                if(i==u->id) break ;
            }
            return ;
        }
        else
        {
            dfs(u->id,x,type^3) ;
            head[type][id]=u->nex ;
            if(ans[x]) return ;
        }
    }
}
 
vector<int> v[maxn] ;
void build_graph(int n)
{
    sort(p+1,p+n+1,cmp1) ;
    for(int i=1;i<n;i++) if(p[i].x==p[i+1].x)
        v[p[i].id].push_back(p[i+1].id) ,
        v[p[i+1].id].push_back(p[i].id) ;
    sort(p+1,p+n+1,cmp2) ;
    for(int i=1;i<n;i++) if(p[i].y==p[i+1].y)
        v[p[i].id].push_back(p[i+1].id) ,
        v[p[i+1].id].push_back(p[i].id) ;
}
 
void dfs2(int x,int f=-1,int c=1)
{
    ans[x]=c ;
    for(auto i : v[x]) if(i!=f)
        dfs2(i,x,3-c) ;
}
 
main()
{
    if(fopen("in","r")) freopen("in","r",stdin) ;
 
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y) ;
        p[i].id=i ;
        add_node(1,p[i].x,i) ;
        add_node(2,p[i].y,i) ;
        nd[1][i]=head[1][p[i].x] ;
        nd[2][i]=head[2][p[i].y] ;
    }
 
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        dfs(i,-1,1) ;
        if(!head[2][p[i].y] || ans[i]) continue ;
        if(!head[2][p[i].y]->nex) continue ;
        dfs(i,-1,2) ;
    }
 
    int n2=0 ;
    for(int i=1;i<=n;i++) if(!ans[i])
        p[++n2]=p[i] ;
    build_graph(n2) ;
 
    memset(vis,0,sizeof(vis)) ;
    for(int i=1;i<=n;i++) if(!ans[i]) dfs2(i) ;
    for(int i=1;i<=n;i++) printf("%c",ans[i]==1?'b':'r') ;
    printf("\n") ;
}
 

沒有留言:

張貼留言