CFR 781 B. Innokenty and a Football League ( 2SAT )
題意:
給 N 個姓名,現在要為每個姓名做縮寫,但希望滿足以下規則:
1. 姓名是 A 的前三個字元,或 A 的前兩個字元接上 B 的第一個字元。
2. 任何縮寫不重複
3. 若對於第 i 個人採取第一種縮寫和第 j 個人採取第一種縮寫會是一樣的,那麼 i 和 j 都不可以採取第一種縮寫。
問是否有合法的方案,有的話輸出。
資料規模:
N ≤ 1000
解法:
一看就覺得很 2SAT,雖然說看了大部份的人的做法都是貪心。
首先一個人要嘛採取第一種縮寫,要嘛採取第二種縮寫,有真/偽的性質。
再來可以討論兩個人衝突的情況進行建邊,u 指向 v 代表若 u 成立則 v 必須成立:
1. 若 i1 和 j1 衝突:
那麼就當作「就算選 i1,也硬是把你變成 i2」:
i1 -> i2
2. 若 i1 和 j2 衝突:
i1 -> j1
3. 若 i2 和 j1 衝突:
i2 -> j2
4. 若 i2 和 j2 衝突:
i2 -> j1
建完邊之後,做一次強連通分量分解。若存在任一對 ( i1, i2 ) 存在於同一個強連通分量,那麼無解,因為同一個強連通分量裡的所有布林值都必須一致。接著要按照拓撲序給各個強連通分量賦植,每次盡量給靠後面的「真」,原因是我們使用的第一種邊。
時間 / 空間複雜度:
O( N )
#include <bits/stdc++.h> using namespace std; const int MAXN = 1000; int N; string A[ MAXN ], B[ MAXN ]; vector< int > G[ MAXN * 2 ], rG[ MAXN * 2 ]; void dfs_topo( int u, vector< int > &stk, vector< int > &vis ){ for( int v : G[ u ] ){ if( vis[ v ] ) continue; vis[ v ] = 1; dfs_topo( v, stk, vis ); } stk.emplace_back( u ); } void dfs_ksrj( int u, vector< int > &scc, const int scc_cnt ){ for( int v : rG[ u ] ){ if( scc[ v ] ) continue; scc[ v ] = scc_cnt; dfs_ksrj( v, scc, scc_cnt ); } } signed main(){ ios::sync_with_stdio( 0 ); { cin >> N; for( int i = 0; i < N; ++i ){ cin >> A[ i ] >> B[ i ]; } } { for( int i = 0; i < N; ++i ){ for( int j = 0; j < N; ++j ){ if( i == j ) continue; if( A[ i ].substr( 0, 3 ) == A[ j ].substr( 0, 3 ) ){ G[ i ].emplace_back( N + i ); rG[ N + i ].emplace_back( i ); } if( A[ i ].substr( 0, 3 ) == A[ j ].substr( 0, 2 ) + B[ j ].substr( 0, 1 ) ){ G[ i ].emplace_back( j ); rG[ j ].emplace_back( i ); } if( A[ i ].substr( 0, 2 ) + B[ i ].substr( 0, 1 ) == A[ j ].substr( 0, 3 ) ){ G[ N + i ].emplace_back( N + j ); rG[ N + j ].emplace_back( N + i ); } if( A[ i ].substr( 0, 2 ) + B[ i ].substr( 0, 1 ) == A[ j ].substr( 0, 2 ) + B[ j ].substr( 0, 1 ) ){ G[ N + i ].emplace_back( j ); rG[ j ].emplace_back( N + i ); } } } } { vector< int > stk, vis( 2 * N ); for( int i = 0; i < 2 * N; ++i ){ if( vis[ i ] ) continue; dfs_topo( i, stk, vis ); } int scc_cnt = 0; vector< int > scc( 2 * N ); for( int i = 2 * N - 1; i >= 0; --i ){ if( scc[ stk[ i ] ] ) continue; scc[ stk[ i ] ] = ++scc_cnt; dfs_ksrj( stk[ i ], scc, scc_cnt ); } for( int i = 0; i < N; ++i ){ if( scc[ i ] == scc[ i + N ] ){ cout << "NO\n"; exit( 0 ); } } vector< int > sat( scc_cnt + 1 ); for( int i = 2 * N - 1; i >= 0; --i ){ int x = scc[ stk[ i ] ]; int y = scc[ stk[ i ] < N ? stk[ i ] + N : stk[ i ] - N ]; if( sat[ x ] ) continue; if( sat[ y ] ){ sat[ x ] = 3 - sat[ y ]; } else{ sat[ x ] = 2; sat[ y ] = 1; } } cout << "YES\n"; for( int i = 0; i < N; ++i ){ if( sat[ scc[ i ] ] == 1 ){ cout << A[ i ].substr( 0, 3 ) << "\n"; } else{ cout << A[ i ].substr( 0, 2 ) + B[ i ].substr( 0, 1 ) << "\n"; } } } return 0; }