作法：
首先當給定的圖不是二部圖時無解。一開始可以把原圖轉換成剩下一堆點和一堆互斥的連接兩點的線段，實際作法也蠻顯然的所以這裡略過。當然如果轉換後出現一個老師要求的學生數集合是空集也顯然無解。我們先處理整張圖裡沒有邊的情形，再把類似的想法套到一般的圖上。
如果現在整張圖裡沒有邊，那麼問題就等價於：有一堆線段，目標要取兩個點 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() ; }
沒有留言:
張貼留言