作法：
首先當給定的圖不是二部圖時無解。一開始可以把原圖轉換成剩下一堆點和一堆互斥的連接兩點的線段，實際作法也蠻顯然的所以這裡略過。當然如果轉換後出現一個老師要求的學生數集合是空集也顯然無解。我們先處理整張圖裡沒有邊的情形，再把類似的想法套到一般的圖上。
如果現在整張圖裡沒有邊，那麼問題就等價於：有一堆線段，目標要取兩個點 X , Y ，使得所有線段均包含 $X$ 或 $Y$ ，且 $t \leq X+Y \leq T$ 。我們先無視 $t$ 和 $T$ 的限制，之後再考慮進來。可以假設 $X \leq Y$ ，那麼 $X$ 必須要 $\leq $所有線段的右端點，否則就會有線段沒有被 $X$ 和 $Y$ 碰到。假設所有線段右端點的最小值為 $R0$ ，所以有 $X \leq R0$ ，也就是等一下我們會考慮 $X$ 從 $R0$ 開始慢慢往左邊跑。如果有一條線段的左端點 $> R0$ ，那麼他之後永遠都不會被 $X$ 碰到，所以就直接把他丟給 $Y$ 去處理（等等 $Y$ 必須要被這條線段包含）。也就是當 $X = R0$ 時，設所有被 $X$ 碰到的線段集合為 $SX$ ，剩下的線段集合為 $SY$ ，那麼 $Y$ 一定要落在 $SY$ 中所有線段的交集裡。如果此時 $SY$ 的交集為空集那麼無解（等等會說明），否則假設現在 $SY$ 的交集為 $[ L , R ]$ ，如果 $R0 + L $ ~ $ R0 + R$ 之間存在一個數介於 $[ t , T ]$ 之間那就找到解了，否則有可能這些數都比 $T$ 大，或是這些數都比 $t$ 小。當 $X$ 慢慢往左移時，假設 $SX$ 中擁有左端點最大值的線段為 $[ L1 , R1 ] $，那麼 $X$ 在往左移到 $< L1$ 之前 $SX$ 和 $SY$ 都不會改變，也就是我們能再確認一下 $L1 + L $ ~ $ R0 + R$ 之間是否有一個數介於 $[ t , T ]$ 之間。如果 $X$ 想要往左移到 $< L1$ 的地方，那麼這時就必須要把 $[ L1 , R1 ]$ 丟給右邊處理，也就是從 $SX$ 中移除 $[ L1 , R1 ]$ ，並在 $SY$ 中加入 $[ L1 , R1 ]$ ，然後繼續重複上述過程（當 $[ L1 , R1 ]$ 被丟到右邊時，$X$ 的往左可移動範圍就變大了）。而這邊就可以注意到，對於 $SY$ 來說，他裡面的線段數量會越來越多，也就是 $SY$ 中所有線段的交集會越來越小，因此當 $x = R0$ 時 $SY$ 交集就已經是空集合的時候就直接無解了。另外還可以注意到，如果前面我們發現到 $R0 + L $ ~ $ R0 + R$ 之間的所有數都比 $t$ 小，那麼之後也是無解的，因為 $[ L , R ]$ 只會越來越往裡面縮，而 $X$ 則是往越來越小的方向跑，也就是不管怎麼樣我們之後找到的解的兩數和一定都會比$ t $小，所以就可以直接判掉了。
再來我們要改進上面的算法來解決原本的問題(原圖為一堆互斥的線段)。假設有一對互相仇視的老師 $[ l , r ]$ 和 $[ l2 , r2 ]$ ，並且 $l \leq l2$ ，那麼可以分成幾種情形：
1. $r < l2$
2. $l2 \leq r $且$ r2 \geq r$
3. $l2 \leq r $且$ r2 < r$
對於第1種情形，可以得到 $[ l , r ]$ 一定是要被放在 $SX$ 裡的，還有 $[ l2 , r2 ]$ 一定要被放在 $SY$ 裡。而對於第2種情形，可以簡單的證明如果存在一個解，使得 $[ l , r ]$ 包含 $Y$ 且 $[ l2 , r2 ]$ 包含 $X$ ，那麼 $[ l , r ]$ 和 $[ l2 , r2 ]$ 都包含了 $X$ 和 $Y$ ，也就是我們也可以直接把 $[ l , r ]$ 丟給 $SX$ ， $[ l2 , r2 ]$ 丟給 $SY$ 。而這裡跟剛剛不一樣的點在於，當之後我們要從 $SX$ 裡拿線段出來丟到 $SY$ 時，前兩種情況的 $[ l , r ]$ 都是不可以被丟到 $SY$ 的，否則就會和條件矛盾，因此要作個標記，當準備要把這種線段丟棄時，就代表 $X$ 不能再往左邊了，就必須要直接 break 掉。至於第3種情形比較麻煩，當我們算出前一段所說的點 $R0$ 時，如果 $R0 \geq l2$ ，那麼這時可以把 $[ l , r ]$ 或 $[ l2 , r2 ]$ 丟到 $SY$ ，因為當 $X = R0$ 時 $X$ 可以負責 $[ l , r ]$ 或 $[ l2 , r2 ]$ ，但此時對 $X$ 來說負責哪條線段其實沒差，所以我們可以先把 $[ l , r ]$ 丟到 $SY$ 裡。或是此時 $R0$ 已經 $< l2$ 了，那麼就勢必要把 $[ l , r ]$ 丟進 $SX$ ，把 $[ l2 , r2 ]$ 丟進 $SY$ ，並且把 $[ l , r ]$ 標記為不可移除，這種情況比較好處理。如果是上一種情況，並且當我們打算在 $SX$ 中移除掉 $[ l2 , r2 ]$ 時，這時作的動作就會變成把 $[ l2 , r2 ]$ 從 $SX$ 丟進 $SY$ ，然後把 $[ l , r ]$ 從 $SY$ 丟進 $SX$ ，因為必須要滿足題目條件。這樣也有機會讓 $X$ 的可移動範圍變大，並且也可以符合題目的條件，所以是沒有問題的。
因此最終的算法和原本的算法只差在會需要判蠻多條件的，至於要怎麼輸出解，我們會需要一個函式把原圖中的一整個連通塊的顏色都反過來，而這只要對於一個 $( l , r , l2 , r2 )$ 多紀錄原始連通塊中的任意一個點就可以了。
code :
#include<bits/stdc++.h> #define INF 1100000000 using namespace std; const int maxn=100000+10 ; void EXIT(){printf("IMPOSSIBLE\n") ; exit(0) ;} int n,col[maxn] ; void SUCCESS(int x,int y) { printf("POSSIBLE\n%d %d\n",x,y) ; for(int i=1;i<=n;i++) printf("%d",col[i]) ; printf("\n") ; exit(0) ; } int L[maxn],R[maxn] ; vector<int> v[maxn] ; void inv(int x,int c) { col[x]=c ; for(auto i : v[x]) if(col[i]==c) inv(i,3-c) ; } void inv(int x){inv(x,3-col[x]) ;} void dfs(int x,int c,int &l1,int &r1,int &l2,int &r2) { col[x]=c ; if(c==1) l1=max(l1,L[x]) , r1=min(r1,R[x]) ; else l2=max(l2,L[x]) , r2=min(r2,R[x]) ; for(auto i : v[x]) { if(col[i]==-1) dfs(i,3-c,l1,r1,l2,r2) ; else if(col[i]==c) EXIT() ; } } struct P { int l,r,l2,r2,start ; bool operator < (const P &rhs) const { return l==rhs.l ? r<rhs.r : l<rhs.l ; } }; multiset<P> le ; multiset<int> rir ; multiset<int,greater<int> > ril ; P p[maxn] ; int tcnt,start[maxn] ; main() { int t,T,m ; scanf("%d%d%d%d",&t,&T,&n,&m) ; for(int i=1;i<=n;i++) { scanf("%d%d",&L[i],&R[i]) ; if(L[i]>T) EXIT() ; } while(m--) { int x,y ; scanf("%d%d",&x,&y) ; v[x].push_back(y) ; v[y].push_back(x) ; } memset(col,-1,sizeof(col)) ; for(int i=1;i<=n;i++) if(col[i]==-1) { start[tcnt]=i ; if(v[i].empty()) p[tcnt++]=(P){L[i],R[i],-1,-1,-1} ; else { int l1,r1,l2,r2 ; l1=l2=-INF ; r1=r2=INF ; dfs(i,1,l1,r1,l2,r2) ; if(l1>r1 || l2>r2) EXIT() ; if(r1>r2) swap(l1,l2) , swap(r1,r2) , inv(i) ; p[tcnt++]=(P){l1,r1,l2,r2,i} ; } } int nowl=INF ; for(int i=0;i<tcnt;i++) nowl=min(nowl,p[i].r) ; for(int i=0;i<tcnt;i++) { int x=start[i] ; if(p[i].l2==-1) { if(p[i].l<=nowl) col[x]=1 , le.insert(p[i]) ; else col[x]=2 , ril.insert(p[i].l) , rir.insert(p[i].r) ; } else if(p[i].l2<p[i].l) { if(p[i].l<=nowl) le.insert(p[i]) , ril.insert(p[i].l2) , rir.insert(p[i].r2) ; else if(nowl>=p[i].l2) inv(x) , le.insert((P){p[i].l2,p[i].r2,-2,-2,-1}) , ril.insert(p[i].l) , rir.insert(p[i].r) ; else EXIT() ; } else if(p[i].l<=nowl) le.insert((P){p[i].l,p[i].r,-2,-2,-1}) , ril.insert(p[i].l2) , rir.insert(p[i].r2) ; else EXIT() ; } if(ril.empty()) SUCCESS(min(T,nowl),T-min(T,nowl)) ; if( (*rir.begin())<(*ril.begin()) ) EXIT() ; if(nowl+(*rir.begin()) < t) EXIT() ; if(nowl+(*ril.begin()) <= T ) SUCCESS(nowl,max(t-nowl,*ril.begin())) ; while(!le.empty()) { auto it=le.end() ; it-- ; if(T-(*ril.begin()) >= it->l) SUCCESS(T-(*ril.begin()),*ril.begin()) ; if(it->l2 == -2) EXIT() ; inv(it->start) ; if(it->l2 == -1) ril.insert(it->l) , rir.insert(it->r) , le.erase(it) ; else { auto tmp=*it ; le.erase(it) ; le.insert((P){tmp.l2,tmp.r2,-2,-2,-1}) ; ril.erase(ril.find(tmp.l2)) ; rir.erase(rir.find(tmp.r2)) ; ril.insert(tmp.l) ; rir.insert(tmp.r) ; } if( (*rir.begin())<(*ril.begin()) ) EXIT() ; } EXIT() ; }
沒有留言:
張貼留言