POJ 3683 Paiest John's Busiest Day(2-sat:Tarjan+Topo)

Description

有一个小镇上只有一个牧师。这个小镇上有一个传说，在九月一日结婚的人会受到爱神的保佑，但是要牧师举办一个仪式。这个仪式要么在婚礼刚刚开始的时候举行，要么举行完婚礼正好结束。
现在已知有n场婚礼，告诉你每一场的开始和结束时间，以及举行仪式所需要的时间。问牧师能否参加所有的婚礼，如果能则输出一种方案.

2-sat

①输入+初始化 input() + initial()

②添边 add_edge()

③缩点 Tarjan()

④判可行否 judge()

⑤若可行，记下超点的对立点

⑥反向建边拓扑染色：

遍历所有的点

对于每个点:

若与他相连接的点跟它本身不处于同一个强连通分量中

将两个强连通分量(即两个超点)反向建边

进行BFS拓扑染色

Code

#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;

struct time
{
    int start, over;
} tm[N];

stack<int> st;
vector<int> v[N];///Trajan用
vector<int> e[N];///Topo用

///弄明白t跟num!
int n, m, t, num;///num:强连通分量(连通块)的个数,缩点后点的个数

bool vis[N];///该点是否访问过
int inst[N];///该点是否在栈中

int time[N];///i点第一次被访问的时间
int low[N];///i点所在强连通分量子图中第一个被搜到的点的time值

int ltt[N];///i点属于第几个强连通分量(0表示不属于任何一个)
int OPP[N];///超点的对立点

int in[N];
int color[N];///拓扑染色,下标是超点!

void Tarjan(int x)///搜索x点及其子树
{
    int temp;
    st.push(x);
    inst[x] = vis[x] = 1;
    low[x] = time[x] = ++t;
    for(int i = 0; i < v[x].size(); i++)
    {
        temp = v[x][i];
        if(vis[temp] == 0)
        {
            Tarjan(temp);
            low[x] = min(low[x], low[temp]);
        }
        else if(inst[temp] == 1)///成环时
            low[x] = min(low[x], time[temp]);
        else///点temp访问过却不在当前栈里：属于已发现的强连通分量
            continue;///这两个不能合二为一的原因：只有从此指彼的单向路
    }
    if(low[x] == time[x])
    {
        num++;///找到第num个强连通分量
        while(!st.empty())
        {
            temp = st.top();
            st.pop();
            ltt[temp] = num;///temp结点属于第num个强连通分量
            inst[temp] = 0;
            if(temp == x)
                break;
        }
    }
}

bool Error(int a, int b)
{
    if(tm[a].start >= tm[b].over || tm[b].start >= tm[a].over)
        return 0;
    return 1;
}

void Topo()
{
    memset(in, 0, sizeof(in));
    memset(color, -1, sizeof(color));

    ///遍历所有的点
    ///对于每个点:
    ///若与他相连接的点跟它本身不处于同一个强连通分量中
    ///将两个强连通分量(即两个超点)反向建边
    ///进行BFS拓扑染色
    for(int i = 1; i <= 2 * n; ++i)
        for(int j = 0; j < v[i].size(); ++j)///多个vector注意区分清楚
        {
            int tem = v[i][j];
            if(ltt[i] == ltt[tem])
                continue;
            e[ ltt[tem] ].push_back(ltt[i]);
            in[ ltt[i] ]++;
        }

    queue<int> q;
    for(int i = 1; i <= num; ++i)
        if(!in[i])
            q.push(i);

    while(!q.empty())
    {
        int tem = q.front();
        q.pop();
        if(color[tem] == -1)
        {
            color[tem] = 1;
            color[ OPP[tem] ] = 0;
        }
        for(int i = 0; i < e[tem].size(); ++i)
        {
            in[ e[tem][i] ]--;
            if(in[ e[tem][i] ] == 0)
                q.push(e[tem][i]);
        }
    }
}

void init()///只一组数据无需init()
{
    t = num = 0;
    memset(vis, 0, sizeof(vis));
    memset(inst, 0, sizeof(inst));
    memset(time, 0, sizeof(time));
    memset(low, 0, sizeof(low));
    memset(ltt, 0, sizeof(ltt));
    memset(color, -1, sizeof(color));
}

///强连通分量内元素个数最少为1(该元素本身)
///这意味着每个元素都有从属的强连通分量

int main()
{
    scanf("%d", &n);

    ///①init();
    ///②input();
    int ssh, ssm, eeh, eem, len;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d:%d %d:%d %d", &ssh, &ssm, &eeh, &eem, &len);
        tm[i].start = ssh * 60 + ssm;
        tm[i].over = tm[i].start + len;
        tm[i + n].over = eeh * 60 + eem;
        tm[i + n].start = tm[i + n].over - len;
    }

    ///③add_edge();
    ///注意此题跟 POJ 3207 的不同
    ///那题一冲突都冲突，这题不一样
    int addnum = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)///跟之前那题不一样,必须这么写!!!
        {
            if(i == j)
                continue;
            if(Error(i, j))
                v[i].push_back(j + n);
            if(Error(i, j + n))
                v[i].push_back(j);
            if(Error(i + n, j))
                v[i + n].push_back(j + n);
            if(Error(i + n, j + n))
                v[i + n].push_back(j);
        }

    ///④Tarjan();
    for(int i = 1; i <= 2 * n; ++i)
        if(!vis[i])
            Tarjan(i);

    ///⑤judge();
    for(int i = 1; i <= n; ++i)
    {
        if(ltt[i] == ltt[i + n])
        {
            cout << "NO" << '\n';
            return 0;
        }
        OPP[ ltt[i] ] = ltt[i + n];///之前傻地写成OPP[ ltt[i] ] = OPP[ ltt[i + n] ];
        OPP[ ltt[i + n] ] = ltt[i];
    }
    cout << "YES" << '\n';

    ///⑥Topo();
    Topo();

    for(int i = 1; i <= n; ++i)
    {
        if(color[ ltt[i] ])///color 里下标是超点
            printf("%.2d:%.2d %.2d:%.2d\n", tm[i].start / 60, tm[i].start % 60, tm[i].over / 60, tm[i].over % 60);
        else
            printf("%.2d:%.2d %.2d:%.2d\n", tm[i+n].start / 60, tm[i+n].start % 60, tm[i+n].over / 60, tm[i+n].over % 60);
    }
    return 0;
}

Kosaraju算法

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 10005;

int n;
vector<int> vs;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> nv[MAX_V];

struct time
{
    int start, over;
} tm[MAX_V];


bool used[MAX_V];
int cmp[MAX_V];

void add_eage(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void DFS(int v)
{
    used[v] = 1;
    for(int i = 0; i < G[v].size(); ++i)
        if(!used[ G[v][i] ])
            DFS(G[v][i]);
        vs.push_back(v);
}

void rDFS(int v, int k)
{
    used[v] = 1;
    cmp[v] = k;
    for(int i = 0; i < rG[v].size(); ++i)
        if(!used[ rG[v][i] ])
            rDFS(rG[v][i], k);
}

int scc()
{
    memset(used, 0, sizeof(used));
    vs.clear();
    for(int v = 1; v <= n; ++v)
        if(!used[v])
            DFS(v);
    memset(used, 0, sizeof(used));
    int k = 0;
    for(int i = vs.size() - 1; i >= 0; --i)
        if(!used[vs[i]])
            rDFS(vs[i], ++k);
    return k;
}

bool Error(int a, int b)
{
    if(tm[a].start >= tm[b].over || tm[b].start >= tm[a].over)
        return 0;
    return 1;
}

int main()
{
    scanf("%d", &n);
    int ssh, ssm, eeh, eem, len;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d:%d %d:%d %d", &ssh, &ssm, &eeh, &eem, &len);
        tm[i].start = ssh * 60 + ssm;
        tm[i].over = tm[i].start + len;
        tm[i + n].over = eeh * 60 + eem;
        tm[i + n].start = tm[i + n].over - len;
    }

    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)///跟之前那题不一样,必须这么写!!!
        {
            if(i == j)
                continue;
            if(Error(i, j))
                add_eage(i, j + n);
            if(Error(i, j + n))
                add_eage(i, j);
            if(Error(i + n, j))
                add_eage(i + n, j + n);
            if(Error(i + n, j + n))
                add_eage(i + n, j);
        }

    int num = scc();
    for(int i = 1; i <= n; i++)
        if(cmp[i] == cmp[i + n])
        {
            puts("NO");
            return 0;
        }

    puts("YES");
    for(int i = 1; i <= n; i++)
    {
        if(cmp[i] > cmp[i + n]) // 在仪式开始时举行
            printf("%.2d:%.2d %.2d:%.2d\n", tm[i].start / 60, tm[i].start % 60, tm[i].over / 60, tm[i].over % 60);
        else
            printf("%.2d:%.2d %.2d:%.2d\n", tm[i+n].start / 60, tm[i+n].start % 60, tm[i+n].over / 60, tm[i+n].over % 60);
    }
    return 0;
}