poj3683

发表于 | 分类于

昨天做这道题的时候各种错误，今天早上终于调好了。

原来也刷过几道2-sat的题，不过输出方案的这是第一道。本来2-sat输出方案的传统做法是先缩点，再建反图拓扑排个序，然后再染色，将红色点输出，然而昨天查资料的时候发现，其实在tarjan求强连通的时候，每个强联通分量的求出顺序就是原图的逆拓扑序！所以我们根本就不用再拓扑排序。接着，根据对称性，若原题有解的话，根据2-sat的对称性，我们只需在两个对应点之间找所属强连通分量时间戳更小的就行了，这样得出的就一定是一组可行解。

题目链接。

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
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
int n;
int tot,had[3000],nxt[5000000],point[5000000];
struct wed{
    int bg;
    int nd;
}p[2003];
inline void add(int x,int y)
{
    tot++;
    point[tot]=y;
    nxt[tot]=had[x];
    had[x]=tot;
}
bool vis[3000];
int t;
int timel;
int dfn[3000],low[3000];
int blng[3000];//强连通分量时间戳 
stack<int>ss;
int ans[2009];
void tarjan(int x)
{
    dfn[x]=low[x]=++t;
    vis[x]=t;
    ss.push(x);
    for(int i=had[x];i;i=nxt[i])
    {
        int to=point[i];
        if(!dfn[to])
        {
            tarjan(to);
            low[x]=min(low[x],low[to]);
        }
        else if(vis[to]) low[x]=min(low[x],dfn[to]);
    }
    if(low[x]==dfn[x])
    {
        timel++;
        while(!ss.empty())
        {
            int y=ss.top();
            vis[y]=0;
            ss.pop();
            blng[y]=timel;
            if(y==x)break;
        }
    }
}
int main()
{
    cin>>n;
    for(int  i=0;i<n;i++)//处理读入 
    {
        int x1,x2,y1,y3,len;
        char c;
        cin>>x1>>c>>x2;
        cin>>y1>>c>>y3>>len;
        p[i<<1].bg=x1*60+x2;
        p[i<<1].nd=p[i<<1].bg+len;
        p[(i<<1)+1].bg=y1*60+y3-len;
        p[(i<<1)+1].nd=p[(i<<1)+1].bg+len;
    }
    for(int i=0;i<2*n;i++)//建图 
        for(int j=i+1;j<2*n;j++)
            if(p[i].bg>=p[j].bg&&p[i].bg<p[j].nd)
            {
                add(i,j^1);
                add(j,i^1);
            }
            else
                if(p[j].bg>=p[i].bg&&p[j].bg<p[i].nd)
                {
                    add(j,i^1);
                    add(i,j^1);
                }
    for(int i=0;i<2*n;i++)//tarjan缩点 
        if(!dfn[i])tarjan(i);
    for(int i=0;i<2*n;i+=2)//判断是否有解 
        if(blng[i]==blng[i+1])
        {
            cout<<"NO";
            return 0;
        }
    for(int i=0;i<2*n;i+=2)//在对应点中选取所属时间戳小的 
        if(blng[i]<blng[i+1])ans[i/2]=i;
        else ans[i/2]=i+1;
    cout<<"YES\n";
    for(int i=0;i<n;i++)//处理并输出 
        printf("%02d:%02d %02d:%02d\n",p[ans[i]].bg/60,p[ans[i]].bg%60,p[ans[i]].nd/60,p[ans[i]].nd%60);
    return 0;
}

这题还有一个坑点就是若一场婚礼的结束时间与下一场婚礼的开始时间是一样的的话，我们认为这不冲突。为了这个WA了一次。。。