連結：http://poj.org/problem?id=3683
題意：有n個婚禮需要主持。每個婚禮有兩個時間段可以主持，求一個時間不沖突的主持n個婚禮的時間安排方案。
思路：顯然是個2-SAT題，若将每個婚禮的兩個時間段視為一個集合的兩個元素，問題轉化為從n個集合裡選n個元素，并且某些元素有互斥關系。很明顯的2-SAT問題。先按選誰必須選誰的方式構圖，然後tarjan縮點。縮完點後，如果有集合的兩個元素在同一強連通分量中，則無解。否則，有兩種尋找方案的方法。第一種是将獲得的縮點之間建反向邊，拓撲排序的同時進行标記。即拓撲排序到u點時，如果u點沒确定選不選，那就選（結論，記住即可。），并将其集合的另一個元素所在的縮點标記為不選。第二種方法，直接比較一個集合兩個元素tarjan縮點的點值，誰的值更小，說明選其影響更小（這也是反向拓撲排序的原因）。
PS：改了半天（是真的半天），最後發現建原圖的時候，選擇的方式錯了，應該按選誰必選誰的方式，我按的是不選誰必不選誰的方式。。。。。。。。。。。。。。。。。MD。。。。。。。心累。。。。。。。還是自己沒了解算法。。。。。。。。。。。。。。。。。
第一種：
#include <cstdio>
#include <queue>
#define ll long long
using namespace std;
const int N = 2e3+10;
const int M = 5e6+10;
int n;
bool no;
struct node { int l,r; }weds[N];
struct Edge { int to,nxt; };
struct Two_Sat
{
int in[N],oppo[N],head1[N],cnt1,head[N],cnt,dfn[N],id,low[N],color[N],cl,sta[N],top,book[N];;
//in[i]:縮點i的入度
//oppo[i]:點i所在集合另一進制素所在的縮點值
//color[i]:點i所在縮點值
bool vis[N];
struct Edge G[M],G1[M];
inline void init()//初始化
{
no=0;
cl=cnt=cnt1=id=top=0;
for(int i=0;i<2*n;i++) in[i]=vis[i]=dfn[i]=0,book[i]=head[i]=head1[i]=-1;
}
inline void add(int u,int v)
{
G[cnt].to=v,G[cnt].nxt=head[u],head[u]=cnt++;
}
inline void add1(int u,int v)
{
G1[cnt1].to=v,G1[cnt1].nxt=head1[u],head1[u]=cnt1++;
}
inline void tarjan(int u)//tarjan強連通分量縮點
{
int v;
dfn[u]=low[u]=++id; vis[u]=1; sta[++top]=u;
for(int i=head[u];i!=-1;i=G[i].nxt)
{
v=G[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u])
{
color[u]=++cl;
while(sta[top]!=u)
{
color[sta[top]]=cl; vis[sta[top--]]=0;
}
vis[sta[top--]]=0;
}
}
inline void Tarjan()
{
for(int i=0;i<2*n;i++)
if(!dfn[i]) tarjan(i);
}
inline void SetOppo()//确定每個元素的同集合元素的縮點值
{
for(int i=0;i<2*n;i+=2)
{
if(color[i]==color[i^1]) { no=1; break; }
oppo[color[i]]=color[i^1],oppo[color[i^1]]=color[i];
}
}
inline bool topo()//拓撲排序，同時确定确定選哪個
{
int u,v;
//先建縮點反向圖
for(u=0;u<2*n;u++)
for(int i=head[u];i!=-1;i=G[i].nxt)
{
v=G[i].to;
if(color[v]==color[u]) continue;
add1(color[v],color[u]),in[color[u]]++;
}
queue<int> q;
for(int i=1;i<=cl;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
u=q.front(); q.pop();
//沒有确定選不選就一定選
if(book[u]==-1) book[u]=1,book[oppo[u]]=0;
for(int i=head1[u];i!=-1;i=G1[i].nxt)
{
v=G1[i].to;
if(--in[v]==0) q.push(v);
}
}
return 1;
}
inline void print()
{
for(int i=0;i<2*n;i++)
{
if(book[color[i]]==1)
printf("%02d:%02d %02d:%02d\n",weds[i].l/60,weds[i].l%60,weds[i].r/60,weds[i].r%60);
}
}
}two;
inline bool ok(node a,node b)
{
if(a.r<=b.l||b.r<=a.l) return 1;
return 0;
}
int main(void)
{
int hl,ml,hr,mr,d;
while(~scanf("%d",&n))
{
two.init();
for(int i=0;i<2*n;i+=2)
{
scanf("%02d:%02d %02d:%02d %d",&hl,&ml,&hr,&mr,&d);
weds[i].l=hl*60+ml; weds[i].r=weds[i].l+d;
weds[i^1].r=hr*60+mr; weds[i^1].l=weds[i^1].r-d;
}
for(int i=0;i<2*n;i+=2)
for(int j=i+2;j<2*n;j+=2)
{
if(!ok(weds[i],weds[j]))
two.add(i,j^1),two.add(j,i^1);
if(!ok(weds[i],weds[j^1]))
two.add(i,j),two.add(j^1,i^1);
if(!ok(weds[i^1],weds[j]))
two.add(i^1,j^1),two.add(j,i);
if(!ok(weds[i^1],weds[j^1]))
two.add(i^1,j),two.add(j^1,i);
}
two.Tarjan();
two.SetOppo();
if(no){ printf("NO\n"); continue;}
printf("YES\n");
two.topo();
two.print();
}
return 0;
}
第二種：
#include <cstdio>
#include <queue>
#define ll long long
using namespace std;
const int N = 2e3+10;
const int M = 5e6+10;
int n;
bool book[N];
bool no;
struct node { int l,r; }weds[N];
struct Edge { int to,nxt; };
struct Two_Sat
{
int in[N],oppo[N],head1[N],cnt1,head[N],cnt,dfn[N],id,low[N],color[N],cl,sta[N],top;
//in[i]:縮點i的入度
//oppo[i]:點i所在集合另一進制素所在的縮點值
//color[i]:點i所在縮點值
bool vis[N];
struct Edge G[M],G1[M];
inline void init()//初始化
{
no=0;
cl=cnt=cnt1=id=top=0;
for(int i=0;i<2*n;i++) book[i]=in[i]=vis[i]=dfn[i]=0,head[i]=head1[i]=-1;
}
inline void add(int u,int v)//原圖建邊
{
G[cnt].to=v,G[cnt].nxt=head[u],head[u]=cnt++;
}
inline void add1(int u,int v)//縮點後，反向建圖
{
G1[cnt1].to=v,G1[cnt1].nxt=head1[u],head1[u]=cnt1++;
}
inline void tarjan(int u)//tarjan強連通分量縮點
{
int v;
dfn[u]=low[u]=++id; vis[u]=1; sta[++top]=u;
for(int i=head[u];i!=-1;i=G[i].nxt)
{
v=G[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u])
{
color[u]=++cl;
while(sta[top]!=u)
{
color[sta[top]]=cl; vis[sta[top--]]=0;
}
vis[sta[top--]]=0;
}
}
inline void Tarjan()
{
for(int i=0;i<2*n;i++)
if(!dfn[i]) tarjan(i);
}
inline void SetOppo()//确定每個元素的同集合元素的縮點值
{
for(int i=0;i<2*n;i+=2)
{
if(color[i]==color[i^1]) { no=1; break; }//其實這種情況不存在
oppo[color[i]]=color[i^1],oppo[color[i^1]]=color[i];
}
}
inline bool topo()
{
int u,v;
//建縮點反向圖
for(u=0;u<2*n;u++)
for(int i=head[u];i!=-1;i=G[i].nxt)
{
v=G[i].to;
if(color[v]==color[u]) continue;
add1(color[v],color[u]),in[color[u]]++;
}
queue<int> q;
for(int i=1;i<=cl;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
u=q.front(); q.pop();
//沒有确定選不選就一定選
if(book[u]==-1) book[u]=1,book[oppo[u]]=0;
for(int i=head1[u];i!=-1;i=G1[i].nxt)
{
v=G1[i].to;
if(--in[v]==0) q.push(v);
}
}
return 1;
}
inline void solve()
{
//根據強連通分量的縮點值，确定選誰。
for(int i=0;i<2*n;i+=2)
{
if(color[i]<color[i^1]) book[i]=1;
else book[i^1]=1;
}
}
inline void print()
{
for(int i=0;i<2*n;i++)
{
if(book[i])
printf("%02d:%02d %02d:%02d\n",weds[i].l/60,weds[i].l%60,weds[i].r/60,weds[i].r%60);
}
}
}two;
inline bool ok(node a,node b)
{
if(a.r<=b.l||b.r<=a.l) return 1;
return 0;
}
int main(void)
{
int hl,ml,hr,mr,d;
while(~scanf("%d",&n))
{
two.init();
for(int i=0;i<2*n;i+=2)
{
scanf("%02d:%02d %02d:%02d %d",&hl,&ml,&hr,&mr,&d);
weds[i].l=hl*60+ml; weds[i].r=weds[i].l+d;
weds[i^1].r=hr*60+mr; weds[i^1].l=weds[i^1].r-d;
}
//建原圖
for(int i=0;i<2*n;i+=2)
for(int j=i+2;j<2*n;j+=2)
{
if(!ok(weds[i],weds[j]))
two.add(i,j^1),two.add(j,i^1);
if(!ok(weds[i],weds[j^1]))
two.add(i,j),two.add(j^1,i^1);
if(!ok(weds[i^1],weds[j]))
two.add(i^1,j^1),two.add(j,i);
if(!ok(weds[i^1],weds[j^1]))
two.add(i^1,j),two.add(j^1,i);
}
two.Tarjan();
two.SetOppo();
if(no){ printf("NO\n"); continue;}
printf("YES\n");
two.solve();
two.print();
}
return 0;
}
![2-SAT點選打開連結 序言概念算法解釋模型題目[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)