poj3683 Priest John's Busiest Day

2-SAT。

读入用了黄学长的快速读入,在此膜拜感谢。

把每对时间当作俩个点。如果有交叉代表相互矛盾。

然后tarjan缩点,这样就能得出当前的2-SAT问题是否有解。

如果有解,跑拓扑排序就能找出一个特定的解。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 5000 + 10;
const int maxm = 2000000 + 10;
inline int read() //by hzwer 实在太好了。。我用下。。跪谢。
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} int g[maxn],v[maxm],next[maxm],eid;
int deg[maxn],g2[maxn],v2[maxm],next2[maxm],eid2;
int color[maxn],cid;
int vis[maxn];
int dfn[maxn],low[maxn],vid;
int s[maxn],sp;
int a[maxn],b[maxn];
int op[maxn];
int q[maxm],l,r,u;
int c[maxn];
int n; void addedge(int a,int b) {
v[eid]=b; next[eid]=g[a]; g[a]=eid++;
} void addedge2(int a,int b) {
deg[b]++;
v2[eid2]=b; next2[eid2]=g2[a]; g2[a]=eid2++;
} bool con(int x,int y) {
if(b[x]<=a[y] || b[y]<=a[x]) return 0;
return 1;
} void build() {
memset(g,-1,sizeof(g));
n=read();
for(int i=1,t;i<=n;i++) {
a[i<<1]=read();
a[i<<1]=a[i<<1]*60+read();
b[i<<1|1]=read();
b[i<<1|1]=b[i<<1|1]*60+read();
t=read();
b[i<<1]=a[i<<1]+t;
a[i<<1|1]=b[i<<1|1]-t;
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++) if(i!=j) {
if(con(i<<1,j<<1)) {
addedge(i<<1,j<<1|1);
addedge(j<<1,i<<1|1);
}
if(con(i<<1,j<<1|1)) {
addedge(i<<1,j<<1);
addedge(j<<1|1,i<<1|1);
}
if(con(i<<1|1,j<<1)) {
addedge(i<<1|1,j<<1|1);
addedge(j<<1,i<<1);
}
if(con(i<<1|1,j<<1|1)) {
addedge(i<<1|1,j<<1);
addedge(j<<1|1,i<<1);
}
} }
void tarjan(int u) {
dfn[u]=low[u]=++vid;
s[++sp]=u; vis[u]=1;
for(int i=g[u];~i;i=next[i]) {
if(vis[v[i]]==0) {
tarjan(v[i]);
low[u]=min(low[u],low[v[i]]);
}
else if(vis[v[i]]==1) {
low[u]=min(low[u],dfn[v[i]]);
}
} if(dfn[u]==low[u]) {
++cid;
do {
color[s[sp]]=cid;
vis[s[sp]]=2;
}while(s[sp--]!=u);
}
} void dfs(int u) {
if(c[u]) return;
c[u]=-1;
for(int i=g2[u];~i;i=next2[i]) dfs(v2[i]);
} void print(int x) {
printf("%.2d:%.2d %.2d:%.2d\n",a[x]/60,a[x]%60,b[x]/60,b[x]%60);
} void solve() {
for(int i=2;i<=((n<<1)|1);i++) if(!vis[i]) tarjan(i);
for(int i=1;i<=n;i++) {
if(color[i<<1]==color[i<<1|1]) {
printf("NO\n");
return;
}
}
printf("YES\n");
memset(g2,-1,sizeof(g2));
for(int u=2;u<=((n<<1)|1);u++) {
for(int i=g[u];~i;i=next[i]) if(color[u]!=color[v[i]])
addedge2(color[v[i]],color[u]);
} for(int i=1;i<=n;i++) {
op[color[i<<1]]=color[i<<1|1];
op[color[i<<1|1]]=color[i<<1];
} for(int u=1;u<=cid;u++) if(!deg[u]) q[++r]=u; while(r) {
u=q[r--];
if(c[u]) continue;
c[u]=1; dfs(op[u]);
for(int i=g2[u];~i;i=next2[i]) {
deg[v2[i]]--;
if(!deg[v2[i]]) q[++r]=v2[i];
}
}
for(int i=1;i<=n;i++)
if(c[color[i<<1]]==1) print(i<<1);
else print(i<<1|1);
} int main() {
build();
solve();
return 0;
}
上一篇:[转] - linux下socket编程实例


下一篇:2019.04.21 python核心特征