http://poj.org/problem?id=3683
思路:2-SAT，输出任意一组方案，O(m+n)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
int first[],next[],tot,go[];
int First[],Next[],Tot,Go[];
int b[],a[],n,ru[],low[],dfn[];
int op[],belong[],instack[],vis[],st[],c[],col[],sz,num,top;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void Insert(int x,int y){
Tot++;
Go[Tot]=y;
Next[Tot]=First[x];
First[x]=Tot;
}
bool jud(int x,int y){
if (b[x]<=a[y]||a[x]>=b[y]) return ;
else return ;
}
void build(){
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++){
if (jud(i*-,j*)){
insert(i*-,j*-);
insert(j*,i*);
}
if (jud(i*-,j*-)){
insert(i*-,j*);
insert(j*-,i*);
}
if (jud(i*,j*)){
insert(i*,j*-);
insert(j*,i*-);
}
if (jud(i*,j*-)){
insert(i*,j*);
insert(j*-,i*-);
}
}
}
void init(){
n=read();
for (int i=;i<=n;i++){
a[i*]=read();
a[i*]=a[i*]*+read();
b[i*-]=read();
b[i*-]=b[i*-]*+read();
int x=read();
b[i*]=a[i*]+x;
a[i*-]=b[i*-]-x;
}
}
void tarjan(int x){
low[x]=dfn[x]=++sz;
instack[x]=vis[x]=;st[++top]=x;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (!vis[pur]){
tarjan(pur);
low[x]=std::min(low[x],low[pur]);
}else if (instack[pur]){
low[x]=std::min(low[x],dfn[pur]);
}
}
if (low[x]==dfn[x]){
num++;
while (st[top]!=x){
instack[st[top]]=;
belong[st[top]]=num;
top--;
}
instack[st[top]]=;
belong[st[top]]=num;
top--;
}
}
void Tarjan(){
for (int i=;i<=*n;i++)
if (!vis[i]) tarjan(i);
}
bool judge(){
for (int i=;i<=n;i++)
if (belong[i*]==belong[i*-]) {
puts("NO");
return ;
}
puts("YES");
return ;
}
void dfs(int x){
if (col[x]) return ;col[x]=-;
for (int i=First[x];i;i=Next[i]){
int pur=Go[i];
dfs(pur);
}
}
void topsort(){
int t=;
for (int i=;i<=num;i++)
if (!ru[i]) c[++t]=i;
while (t){
int now=c[t--];
if (col[now]) continue;col[now]=;
dfs(op[now]);
for (int i=First[now];i;i=Next[i]){
int pur=Go[i];
ru[pur]--;
if (ru[pur]==) c[++t]=pur;
}
}
}
void rebuild(){
for (int i=;i<=*n;i++)
for (int j=first[i];j;j=next[j]){
int pur=go[j];
if (belong[pur]==belong[i]) continue;
ru[belong[i]]++;
Insert(belong[pur],belong[i]);;
}
for (int i=;i<=*n;i++)
op[belong[i*]]=belong[i*-],op[belong[i*-]]=belong[i*];
}
void print(int x){
printf("%.2d:",x/);
printf("%.2d ",x%);
}
void Output(){
for (int i=;i<=n;i++)
if (col[belong[i*]]==){
print(a[i*]);print(b[i*]);puts("");
}else{
print(a[i*-]);print(b[i*-]);puts("");
}
}
int main(){
init();
build();
Tarjan();
if (judge()) return ;
rebuild();
topsort();
Output();
}
为什么我会犯用错数组这种错误。。