poj 六道2-sat第三题：

题目描述：有n个婚礼，每个婚礼有起始时间si，结束时间ti，还有一个主持时间ti，ti必须安排在婚礼的开始或者结束，主持由祭祀来做，但是只有一个祭祀，所以各个婚礼的主持时间不能重复，问你有没有可能正常的安排主持时间，不能输出no，能的话要输出具体的答案：即每个婚礼的主持时间段是什么样的。

解题报告：

对于每个婚礼，主持时间只有两种状态，而且各个婚礼之间的主持时间之间有相互限制，所以想到2-sat。

构图：

对于婚礼i和婚礼j。i表示在开始主持，i2表示在结束主持，j类似。

枚举每一对不同的i和j。

如果i和j冲突。连接i j2

如果i和j2冲突，连接i j

如果i2和j冲突，连接i2 j2

如果i2和j2冲突，连接i2 j

然后就是求强联通，topsort，输出答案。

代码如下：

#include<iostream>
using namespace std;
#define size 2100 // 点的个数
#define esize 3000000 // 边的个数
int v[size], cnt, v2[size], cnt2;
struct edge{int from, to, next;}e[esize], e2[esize];
void insert(int from, int to)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].next = v[from]; v[from] = cnt++;
}
void insert2(int from, int to)
{
    e2[cnt2].from = from, e2[cnt2].to = to; e2[cnt2].next = v2[from]; v2[from] = cnt2++;
}
int index, dfn[size], low[size], instack[size], sta[size], top;
int belong[size], cntnum, num[size];
int cf[size], rd[size], que[size], col[size];
bool ans[size];//1表示选择
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    int tmp = v[id];
    while(tmp != -1)
    {
        if (!dfn[e[tmp].to])
        {
            tarjan(e[tmp].to);
            if (low[e[tmp].to] < low[id]) low[id] = low[e[tmp].to];
        }
        else if (instack[e[tmp].to] && dfn[e[tmp].to] < low[id])
            low[id] = dfn[e[tmp].to];
        tmp = e[tmp].next;
    }
    if (dfn[id] == low[id])
    {
        do
        {
            tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = cntnum;
            num[cntnum]++;
        }while(tmp != id);
        cntnum++;
    }
}
bool solve(int n) // n是一半的人数 执行tarjan和topsort,完成标记
{
    index = cntnum = top = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(num, 0, sizeof(num));
    for(int i = 0; i < 2 * n; i++)
        if (!dfn[i]) tarjan(i);
    for(int i = 0; i < n; i++)
    {
        if (belong[i] == belong[i + n]) return false;
        cf[belong[i]] = belong[i + n];
        cf[belong[i + n]] = belong[i];
    }
    memset(rd, 0, sizeof(rd));
    memset(v2, -1, sizeof(v2));
    memset(col, 0, sizeof(col));cnt2 = 0;
    for(int i = 0; i < cnt; i++)
        if (belong[e[i].from] != belong[e[i].to])
        {
            insert2(belong[e[i].to], belong[e[i].from]);
            rd[belong[e[i].from]]++;
        }
    int head = 0, tail = 0;
    for(int i = 0; i < cntnum; i++)
        if (rd[i] == 0) que[tail++] = i;
    while(head < tail)
    {
        int tmp = que[head++];
        if (col[tmp] == 0)
        {
            col[tmp] = 1;
            col[cf[tmp]] = -1;
        }
        int id = v2[tmp];
        while(id != -1)
        {
            if (--rd[e2[id].to] == 0)
                que[tail++] = e2[id].to;
            id = e2[id].next;
        }
    }
    memset(ans, 0, sizeof(ans));
    for(int i = 0; i < 2 * n; i++)
        if (col[belong[i]] == 1) ans[i] = 1;
    return true;
}
int n;
struct elm{int from, to, len;}x[size];
char str[2][10];
int judge(int id)
{
    int num = (str[id][0] - '0') * 10;
    num += (str[id][1] - '0'); num *= 60;
    num += (str[id][3] - '0') * 10 + str[id][4] - '0';
    return num;
}
bool judge2(int from1, int len1, int from2, int len2)
{
    return (from1 < from2 + len2 && from2 < from1 + len1);
}
void judge3(int xx)
{
    printf("%02d:%02d", xx / 60, xx % 60);
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%s%s%d", str[0], str[1], &x[i].len);
        x[i].from = judge(0);
        x[i].to = judge(1);
    }
    memset(v, -1, sizeof(v)); cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            if (i == j) continue;
            if (judge2(x[i].from, x[i].len, x[j].from, x[j].len))
                insert(i, j + n);
            if (judge2(x[i].from, x[i].len, x[j].to - x[j].len, x[j].len))
                insert(i, j);
            if (judge2(x[i].to - x[i].len, x[i].len, x[j].from, x[j].len))
                insert(i + n, j + n);
            if (judge2(x[i].to - x[i].len, x[i].len, x[j].to - x[j].len, x[j].len))
                insert(i + n, j);
        }
    if(solve(n))
    {
        printf("YES\n");
        for(int i = 0; i < n; i++)
            if (ans[i])
            {
                judge3(x[i].from); putchar(' ');
                judge3(x[i].from + x[i].len); putchar('\n');
            }
            else
            {
                judge3(x[i].to - x[i].len); putchar(' ');
                judge3(x[i].to); putchar('\n');
            }
    }
    else printf("NO\n");
    return 0;
}