poj 3683(2-SAT)

poj 3683
1、区间重合的判定
2、想要输出数最少两位可以用”%.2d”输出
例如数是8,但想输出08,就可以用,如果是14,则还是输出14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ms(i,j) memset(i, j, sizeof i);
const int MAXN = 1000 + 5;
struct inv
{
int l, r, time;
}in[MAXN];
struct TwoSAT
{
vector<int> G[MAXN*2];
int S[MAXN*2];
bool mark[MAXN*2];
int n, c;
void init(int n)
{
this->n = n;
for (int i=0;i<=n*2;i++)
{
G[i].clear();
mark[i] = false;
}
}
void ins(int u, int v)
{
G[u].push_back(v);
}
int dfs(int x)
{
if (mark[x^1]) return false;
if (mark[x]) return true;
mark[x] = true;
S[++c] = x;
for (int i=0;i<G[x].size();i++)
{
if (!dfs(G[x][i])) return false;
}
return true;
}
int solve()
{
for (int i=0;i<2*n;i+=2)
if (!mark[i]&&!mark[i+1])
{
c = 0;
if (!dfs(i))
{
while (c>0) mark[S[c--]] = false;
if (!dfs(i+1)) return false;
}
}
return true;
}
}ts;
int n;
int fight(int x1, int y1, int x2, int y2)
{
if (x2>=x1&&x2<y1) return true;
if (y2<=y1&&x1<y2) return true;
return false;
}
void init()
{
for (int i=0;i<n;i++)
{
int h1, h2, m1, m2;
scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &in[i].time);
in[i].l = h1*60+m1;
in[i].r = h2*60+m2;
}
}
void solve()//2*x is left, 2*x+1 is right(~)
{
ts.init(n);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (i!=j)
{
int &x1 = in[i].l, &y1 = in[i].r, &x2 = in[j].l, &y2 = in[j].r, &t1 = in[i].time, &t2 = in[j].time;
if (fight(x1, x1+t1, x2, x2+t2))//l l
{
ts.ins(2*i, 2*j+1);
ts.ins(2*j, 2*i+1);
}
if (fight(x1, x1+t1, y2-t2, y2))//l r
{
ts.ins(2*i, 2*j);
ts.ins(2*j+1, 2*i+1);
}
if (fight(y1-t1, y1, y2-t2, y2))//r r
{
ts.ins(2*i+1, 2*j);
ts.ins(2*j+1, 2*i);
}
if (fight(y1-t1, y1, x2, x2+t2))//r l
{
ts.ins(2*j, 2*i);
ts.ins(2*i+1, 2*j+1);
}
}
if (ts.solve())
{
printf("YES\n");
for (int i=0;i<n;i++)
{
if (ts.mark[i*2])//l
{
int tot = in[i].l + in[i].time;
int h1 = in[i].l / 60, m1 = in[i].l % 60;
int h2 = tot / 60, m2 = tot % 60;
printf("%.2d:%.2d %.2d:%.2d\n", h1, m1, h2, m2);
}
if (ts.mark[i*2+1])//r
{
int tot = in[i].r - in[i].time;
int h1 = in[i].r / 60, m1 = in[i].r % 60;
int h2 = tot / 60, m2 = tot % 60;
printf("%.2d:%.2d %.2d:%.2d\n", h2, m2, h1, m1);
}
}
} else printf("NO\n");
}
int main()
{
while (scanf("%d", &n)==1)
{
init();
solve();
}
return 0;
}

------ 本文结束 ------