http://poj.org/problem?id=3683
思路:2-SAT，输出任意一组方案，O(m+n)
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 int first[2000005],next[2000005],tot,go[2000005]; 7 int First[2000005],Next[2000005],Tot,Go[2000005]; 8 int b[200005],a[200005],n,ru[200005],low[200005],dfn[200005]; 9 int op[2000005],belong[200005],instack[200005],vis[200005],st[200005],c[200005],col[200005],sz,num,top; 10 int read(){ 11 int t=0,f=1;char ch=getchar(); 12 while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} 13 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 14 return t*f; 15 } 16 void insert(int x,int y){ 17 tot++; 18 go[tot]=y; 19 next[tot]=first[x]; 20 first[x]=tot; 21 } 22 void Insert(int x,int y){ 23 Tot++; 24 Go[Tot]=y; 25 Next[Tot]=First[x]; 26 First[x]=Tot; 27 } 28 bool jud(int x,int y){ 29 if (b[x]<=a[y]||a[x]>=b[y]) return 0; 30 else return 1; 31 } 32 void build(){ 33 for (int i=1;i<=n;i++) 34 for (int j=i+1;j<=n;j++){ 35 if (jud(i*2-1,j*2)){ 36 insert(i*2-1,j*2-1); 37 insert(j*2,i*2); 38 } 39 if (jud(i*2-1,j*2-1)){ 40 insert(i*2-1,j*2); 41 insert(j*2-1,i*2); 42 } 43 if (jud(i*2,j*2)){ 44 insert(i*2,j*2-1); 45 insert(j*2,i*2-1); 46 } 47 if (jud(i*2,j*2-1)){ 48 insert(i*2,j*2); 49 insert(j*2-1,i*2-1); 50 } 51 } 52 } 53 void init(){ 54 n=read(); 55 for (int i=1;i<=n;i++){ 56 a[i*2]=read(); 57 a[i*2]=a[i*2]*60+read(); 58 b[i*2-1]=read(); 59 b[i*2-1]=b[i*2-1]*60+read(); 60 int x=read(); 61 b[i*2]=a[i*2]+x; 62 a[i*2-1]=b[i*2-1]-x; 63 } 64 } 65 void tarjan(int x){ 66 low[x]=dfn[x]=++sz; 67 instack[x]=vis[x]=1;st[++top]=x; 68 for (int i=first[x];i;i=next[i]){ 69 int pur=go[i]; 70 if (!vis[pur]){ 71 tarjan(pur); 72 low[x]=std::min(low[x],low[pur]); 73 }else if (instack[pur]){ 74 low[x]=std::min(low[x],dfn[pur]); 75 } 76 } 77 if (low[x]==dfn[x]){ 78 num++; 79 while (st[top]!=x){ 80 instack[st[top]]=0; 81 belong[st[top]]=num; 82 top--; 83 } 84 instack[st[top]]=0; 85 belong[st[top]]=num; 86 top--; 87 } 88 } 89 void Tarjan(){ 90 for (int i=1;i<=2*n;i++) 91 if (!vis[i]) tarjan(i); 92 } 93 bool judge(){ 94 for (int i=1;i<=n;i++) 95 if (belong[i*2]==belong[i*2-1]) { 96 puts("NO"); 97 return 1; 98 } 99 puts("YES"); 100 return 0; 101 } 102 void dfs(int x){ 103 if (col[x]) return ;col[x]=-1; 104 for (int i=First[x];i;i=Next[i]){ 105 int pur=Go[i]; 106 dfs(pur); 107 } 108 } 109 void topsort(){ 110 int t=0; 111 for (int i=1;i<=num;i++) 112 if (!ru[i]) c[++t]=i; 113 while (t){ 114 int now=c[t--]; 115 if (col[now]) continue;col[now]=1; 116 dfs(op[now]); 117 for (int i=First[now];i;i=Next[i]){ 118 int pur=Go[i]; 119 ru[pur]--; 120 if (ru[pur]==0) c[++t]=pur; 121 } 122 } 123 } 124 void rebuild(){ 125 for (int i=1;i<=2*n;i++) 126 for (int j=first[i];j;j=next[j]){ 127 int pur=go[j]; 128 if (belong[pur]==belong[i]) continue; 129 ru[belong[i]]++; 130 Insert(belong[pur],belong[i]);; 131 } 132 for (int i=1;i<=2*n;i++) 133 op[belong[i*2]]=belong[i*2-1],op[belong[i*2-1]]=belong[i*2]; 134 } 135 void print(int x){ 136 printf("%.2d:",x/60); 137 printf("%.2d ",x%60); 138 } 139 void Output(){ 140 for (int i=1;i<=n;i++) 141 if (col[belong[i*2]]==1){ 142 print(a[i*2]);print(b[i*2]);puts(""); 143 }else{ 144 print(a[i*2-1]);print(b[i*2-1]);puts(""); 145 } 146 } 147 int main(){ 148 init(); 149 build(); 150 Tarjan(); 151 if (judge()) return 0; 152 rebuild(); 153 topsort(); 154 Output(); 155 }
为什么我会犯用错数组这种错误。。