POJ3683（2-SAT+模型1+暴力+scc）

题目链接：https://vjudge.net/problem/POJ-3683

题目意思：有

问：输出是否可以所有新人的仪式时间不重叠

如果可以满足楼上的条件，还需输出方案

题目思路：2-SAT问题模型 1.暴力dfs；2.tarjan流程

暴力在vis数组的大小卡了一下午才找出来... ...（菜鸡行为）不过我就不懂了题目给了1000，为什么2000,3000都不够用，非要两倍大小，别人博客都是2000搞定。难道是因为wa的太多了？

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using std::min;
  5 using std::max;
  6 const int N = 2010;
  7 bool vis[N*2];
  8 int n,cnt,top,S[N],T[N],D[N],sta[N],head[N];
  9 struct E
 10 {
 11     int next,v;
 12 }edge[N*N];
 13 void init()
 14 {
 15     memset(vis,false,sizeof(vis));
 16     memset(head,0,sizeof(head));
 17     memset(S,0,sizeof(S));
 18     memset(T,0,sizeof(T));
 19     memset(D,0,sizeof(D));
 20     memset(sta,0,sizeof(sta));
 21     top = cnt = 0;
 22 }
 23 void add(int u ,int v)
 24 {
 25     edge[++cnt].v = v; 
 26     edge[cnt].next = head[u];
 27     head[u] = cnt;
 28 }
 29 bool dfs(int u)
 30 {
 31     if(vis[u + n]) return false;
 32     if(vis[u]) return true;
 33 //    printf("u = %d
",u);
 34     vis[u] = true;
 35     sta[top ++] = u;
 36     for(int i = head[u];i;i = edge[i].next)
 37     {
 38         if(!dfs(edge[i].v)) return false;
 39     }
 40     return true;
 41 }
 42 bool solve(int n)
 43 {
 44     for(int i = 0;i < n;i ++)
 45     {
 46         for(int j = i + 1;j < n;j ++)
 47         {
 48             if (min(S[i] + D[i], S[j] + D[j]) > max(S[i], S[j])) {
 49                 add(i, j + n);
 50                 add(j, i + n);
 51             }
 52             if (min(S[i] + D[i], T[j]) > max(S[i], T[j] - D[j])) {
 53                 add(i, j);
 54                 add(j + n, i + n);
 55             }
 56             if (min(T[i], S[j] + D[j]) > max(T[i] - D[i], S[j])) {
 57                 add(i + n, j + n);
 58                 add(j, i);
 59             }
 60             if (min(T[i], T[j]) > max(T[i] - D[i], T[j] - D[j])) {
 61                 add(i + n, j);
 62                 add(j + n, i);
 63             }
 64         }
 65     }
 66     for(int i = 0;i < n;i ++)
 67     {
 68         if(!vis[i]&&!vis[i + n])
 69         {
 70             top = 0;
 71 //            printf("shuai！ = %d 
",i);
 72             if(!dfs(i))
 73             {
 74                 while(top) vis[sta[--top]] = false;
 75                 if(!dfs(i + n)) return false;
 76             }
 77         }
 78     }
 79     return true;
 80 }
 81 int main()
 82 {
 83     while(~scanf("%d",&n))
 84     {
 85         init();
 86         for(int i = 0,h1,h2,m1,m2;i < n;i ++)
 87         {
 88             scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&D[i]);
 89             S[i] = h1*60 + m1;
 90             T[i] = h2*60 + m2;
 91         }
 92         
 93         if(solve(n))
 94         {
 95             printf("YES
");
 96             for(int i = 0;i < n;i ++)
 97             {
 98                 if(vis[i]) printf("%02d:%02d %02d:%02d
",S[i]/60,S[i]%60,(S[i] + D[i])/60,(S[i] + D[i])%60);
 99                 else printf("%02d:%02d %02d:%02d
",(T[i] - D[i])/60,(T[i] - D[i])%60,T[i] / 60,T[i] % 60); 
100             }
101         }
102         else printf("NO
");
103     }
104     
105     return 0;
106 }

暴力dfs

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using std::min;
  5 using std::max;
  6 const int N = 2010;
  7 bool vis[N*2];
  8 int n,cnt,top,tot,scc,S[N],T[N],D[N],sta[N],head[N],dfn[N],low[N],belong[N];
  9 struct E
 10 {
 11     int next,v;
 12 }edge[N*N];
 13 void init()
 14 {
 15     memset(vis,false,sizeof(vis));
 16     memset(head,0,sizeof(head));
 17     memset(dfn,0,sizeof(dfn));
 18     memset(low,0,sizeof(low));
 19     memset(sta,0,sizeof(sta));
 20     tot = scc = top = cnt = 0;
 21 }
 22 void add(int u ,int v)
 23 {
 24     edge[++cnt].v = v; 
 25     edge[cnt].next = head[u];
 26     head[u] = cnt;
 27 }
 28 void tarjan(int u)
 29 {
 30     dfn[u] = low[u] = ++tot;
 31     sta[top++] = u;
 32     vis[u] = true;
 33     for(int i = head[u];i;i = edge[i].next)
 34     {
 35         int v = edge[i].v;
 36         if(!dfn[v]) 
 37         {
 38             tarjan(v);
 39             low[v] = min(low[u],low[v]);
 40         }
 41         else if(vis[v])
 42         {
 43             low[u] = min(low[u],dfn[v]);
 44         }
 45     }
 46     if(low[u] == dfn[u])
 47     {
 48         int t;
 49         scc++;
 50         do
 51         {
 52             t = sta[--top];
 53             vis[t] = false;
 54             belong[t] = scc;
 55         }while(t != u);
 56     }
 57 } 
 58 void solve(int n)
 59 {
 60     for(int i = 0;i < n;i ++)
 61     {
 62         for(int j = i + 1;j < n;j ++)
 63         {
 64             if (min(S[i] + D[i], S[j] + D[j]) > max(S[i], S[j])) {
 65                 add(i, j + n);
 66                 add(j, i + n);
 67             }
 68             if (min(S[i] + D[i], T[j]) > max(S[i], T[j] - D[j])) {
 69                 add(i, j);
 70                 add(j + n, i + n);
 71             }
 72             if (min(T[i], S[j] + D[j]) > max(T[i] - D[i], S[j])) {
 73                 add(i + n, j + n);
 74                 add(j, i);
 75             }
 76             if (min(T[i], T[j]) > max(T[i] - D[i], T[j] - D[j])) {
 77                 add(i + n, j);
 78                 add(j + n, i);
 79             }
 80         }
 81     }
 82     for(int i = 0;i < (n<<1);i ++)
 83     {
 84         if(!dfn[i]) tarjan(i);
 85     }
 86     for(int i = 0;i < n;i ++)
 87     {
 88         if(belong[i] == belong[i + n]){
 89             printf("NO
");
 90             return ;
 91         }
 92     }
 93     printf("YES
");
 94     for(int i = 0;i < n;i ++)
 95     {
 96         if(belong[i] < belong[i + n]) printf("%02d:%02d %02d:%02d
",S[i]/60,S[i]%60,(S[i] + D[i])/60,(S[i] + D[i])%60);
 97         else printf("%02d:%02d %02d:%02d
",(T[i] - D[i])/60,(T[i] - D[i])%60,T[i] / 60,T[i] % 60);
 98     }
 99 }
100 int main()
101 {
102     while(~scanf("%d",&n))
103     {
104         init();
105         for(int i = 0,h1,h2,m1,m2;i < n;i ++)
106         {
107             scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&D[i]);
108             S[i] = h1*60 + m1;
109             T[i] = h2*60 + m2;
110         }
111         solve(n);
112     }
113     return 0;
114 }

scc