首页 > 代码库 > poj 3683 Priest John's Busiest Day - 2-sat
poj 3683 Priest John's Busiest Day - 2-sat
<style></style>
John is the only priest in his town. September 1st is the John‘s busiest day in a year because there is an old legend in the town that the couple who get married on that day will be forever blessed by the God of Love. This year N couples plan to get married on the blessed day. The i-th couple plan to hold their wedding from time Sito time Ti. According to the traditions in the town, there must be a special ceremony on which the couple stand before the priest and accept blessings. The i-th couple need Di minutes to finish this ceremony. Moreover, this ceremony must be either at the beginning or the ending of the wedding (i.e. it must be either from Sito Si + Di, or from Ti - Di to Ti). Could you tell John how to arrange his schedule so that he can present at every special ceremonies of the weddings.
Note that John can not be present at two weddings simultaneously.
Input
The first line contains a integer N ( 1 ≤ N ≤ 1000).
The next N lines contain the Si, Ti and Di. Si and Ti are in the format of hh:mm.
Output
The first line of output contains "YES" or "NO" indicating whether John can be present at every special ceremony. If it is "YES", output another N lines describing the staring time and finishing time of all the ceremonies.
Sample Input
208:00 09:00 3008:15 09:00 20
Sample Output
YES08:00 08:3008:40 09:00
2-sat输出任意解。缩点缩完后，建反图，拓扑排序。
注意端点的问题，任意两人的婚礼时间不能重叠。
Code
1 /** 2 * poj 3 * Problem#3683 4 * Accepted 5 * Time:172ms 6 * Memory:17132k 7 */ 8 #include <iostream> 9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const double eps = 1e-6; 33 const int binary_limit = 128; 34 #define smin(a, b) a = min(a, b) 35 #define smax(a, b) a = max(a, b) 36 #define max3(a, b, c) max(a, max(b, c)) 37 #define min3(a, b, c) min(a, min(b, c)) 38 template<typename T> 39 inline boolean readInteger(T& u){ 40 char x; 41 int aFlag = 1; 42 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 43 if(x == -1) { 44 ungetc(x, stdin); 45 return false; 46 } 47 if(x == ‘-‘){ 48 x = getchar(); 49 aFlag = -1; 50 } 51 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 52 ungetc(x, stdin); 53 u *= aFlag; 54 return true; 55 } 56 57 ///map template starts 58 typedef class Edge{ 59 public: 60 int end; 61 int next; 62 Edge(const int end = 0, const int next = 0):end(end), next(next){} 63 }Edge; 64 65 typedef class MapManager{ 66 public: 67 int ce; 68 int *h; 69 vector<Edge> edge; 70 MapManager(){} 71 MapManager(int points):ce(0){ 72 h = new int[(const int)(points + 1)]; 73 memset(h, 0, sizeof(int) * (points + 1)); 74 edge.push_back(Edge()); 75 } 76 inline void addEdge(int from, int end){ 77 // printf("%d->%d\n", from, end); 78 edge.push_back(Edge(end, h[from])); 79 h[from] = ++ce; 80 } 81 inline void addDoubleEdge(int from, int end){ 82 addEdge(from, end); 83 addEdge(end, from); 84 } 85 Edge& operator [] (int pos) { 86 return edge[pos]; 87 } 88 }MapManager; 89 #define m_begin(g, i) (g).h[(i)] 90 ///map template ends 91 92 int n; 93 MapManager g; 94 int *ls, *rs, *lasts; 95 96 inline int readTime() { 97 static int a, b; 98 readInteger(a); 99 readInteger(b);100 return a * 60 + b;101 }102 103 boolean isOn(int l1, int r1, int l2, int r2) {104 // printf("checking:[%d, %d][%d, %d]\n", l1, r1, l2, r2);105 return !(r1 <= l2 || l1 >= r2); // Notice that use ‘<=‘ and ‘>=‘ instead of ‘<‘ and ‘>‘106 }107 108 inline void init() {109 readInteger(n);110 ls = new int[n + 1];111 rs = new int[n + 1];112 lasts = new int[n + 1];113 for(int i = 1; i <= n; i++) {114 ls[i] = readTime();115 rs[i] = readTime();116 readInteger(lasts[i]);117 }118 }119 120 inline void init_map() {121 g = MapManager(2 * n + 3);122 for(int i = 1; i < n; i++) {123 for(int j = i + 1; j <= n; j++) {124 if(isOn(ls[i], ls[i] + lasts[i], ls[j], ls[j] + lasts[j])) {125 g.addEdge(2 * i - 1, 2 * j);126 g.addEdge(2 * j - 1, 2 * i);127 }128 if(isOn(ls[i], ls[i] + lasts[i], rs[j] - lasts[j], rs[j])) {129 g.addEdge(2 * i - 1, 2 * j - 1);130 g.addEdge(2 * j, 2 * i);131 }132 if(isOn(rs[i] - lasts[i], rs[i], ls[j], ls[j] + lasts[j])) {133 g.addEdge(2 * i, 2 * j);134 g.addEdge(2 * j - 1, 2 * i - 1);135 }136 if(isOn(rs[i] - lasts[i], rs[i], rs[j] - lasts[j], rs[j])) {137 g.addEdge(2 * i, 2 * j - 1);138 g.addEdge(2 * j, 2 * i - 1);139 }140 }141 }142 }143 144 int cnt = 0, scc = 0;145 int* visitID;146 int* exitID;147 boolean* visited;148 boolean* instack;149 stack<int> s;150 int* belong;151 inline void init_tarjan() {152 int an = 2 * n + 3;153 visitID = new int[(an)];154 exitID = new int[(an)];155 visited = new boolean[(an)];156 instack = new boolean[(an)];157 belong = new int[(an)];158 memset(visited, false, sizeof(boolean) * an);159 memset(instack, false, sizeof(boolean) * an);160 }161 162 void tarjan(int node) {163 visitID[node] = exitID[node] = cnt++;164 visited[node] = instack[node] = true;165 s.push(node);166 167 for(int i = m_begin(g, node); i; i = g[i].next) {168 int& e = g[i].end;169 if(!visited[e]) {170 tarjan(e);171 smin(exitID[node], exitID[e]);172 } else if(instack[e]) {173 smin(exitID[node], visitID[e]);174 }175 }176 177 if(visitID[node] == exitID[node]) {178 int now = -1;179 scc++;180 while(now != node) {181 now = s.top();182 s.pop();183 instack[now] = false;184 belong[now] = scc;185 }186 }187 }188 189 int* opp;190 int* col;191 int* dag;192 MapManager rg;193 inline void rebuild() {194 delete[] visitID;195 delete[] exitID;196 delete[] visited;197 delete[] instack;198 199 rg = MapManager(scc);200 col = new int[(scc + 1)];201 opp = new int[(scc + 1)];202 dag = new int[(scc + 1)];203 memset(col, 0, sizeof(int) * (scc + 1));204 memset(dag, 0, sizeof(int) * (scc + 1));205 for(int i = 1; i <= (2 * n); i++) {206 if(i & 1) opp[belong[i]] = belong[i + 1];207 else opp[belong[i]] = belong[i - 1];208 for(int j = m_begin(g, i); j; j = g[j].next) {209 if(belong[i] != belong[g[j].end])210 rg.addEdge(belong[g[j].end], belong[i]), dag[belong[i]]++;211 }212 }213 }214 215 void dfs(int node) {216 if(col[node]) return;217 col[node] = 2;218 for(int i = m_begin(rg, node); i; i = rg[i].next)219 dfs(rg[i].end);220 }221 222 queue<int> que;223 inline void topu() {224 for(int i = 1; i <= scc; i++) {225 if(!dag[i])226 que.push(i);227 }228 while(!que.empty()) {229 int e = que.front();230 que.pop();231 if(col[e]) continue;232 col[e] = 1;233 dfs(opp[e]);234 for(int i = m_begin(rg, e); i; i = rg[i].next) {235 int& eu = rg[i].end;236 dag[eu]--;237 if(dag[eu] == 0)238 que.push(eu);239 }240 }241 }242 243 inline void check() {244 for(int i = 1; i < (n << 1); i += 2)245 if(belong[i] == belong[i + 1]) {246 puts("NO");247 exit(0);248 }249 }250 251 inline void printTime(int x) {252 printf("%.2d:%.2d", x / 60, x % 60);253 }254 255 inline void solve() {256 puts("YES");257 for(int i = 1; i <= n; i++) {258 if(col[belong[i * 2 - 1]] == 1) printTime(ls[i]), putchar(‘ ‘), printTime(ls[i] + lasts[i]);259 else printTime(rs[i] - lasts[i]), putchar(‘ ‘), printTime(rs[i]);260 putchar(‘\n‘);261 }262 }263 264 int main() {265 init();266 init_map();267 init_tarjan();268 for(int i = 1; i <= 2 * n; i++)269 if(!visited[i])270 tarjan(i);271 check();272 rebuild();273 topu();274 solve();275 return 0;276 }
poj 3683 Priest John's Busiest Day - 2-sat
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。