[关闭]
@darkproject 2018-02-14T14:10:59.000000Z 字数 7952 阅读 901

dfs及其应用

2018寒假集训

A - The Necklace (UVA - 10054)

每个珠子有2半颜色，问是否能将珠子串起来形成一个环链（珠子之间连接必须保证连接处颜色相同）,将每种颜色看作结点，珠子2半连一条有向边，问题可以转换欧拉回路输出路径。因为珠子可以翻转，可以当作无向图的欧拉回路来做。
以下为存在欧拉回路的条件：（图必须连通）
在无向图中，所有顶点的度数均为偶，则存在 Eularian cycle；若有且仅有两个顶点的度数为奇，其余的都为偶，则存在 Eularian path；
在有向图中，所有顶点的入度数等于出度数，则存在 Eularian cycle；若有且仅有两个顶点：其中一个入度数比出度数大 1，另一个入度数比出度数小 1，其余的顶点入度数等于出度数，则存在 Eularian path.
综上并查集判断图是否连通，fleury求欧拉回路

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn =55;
  7. int t,n;
  8. int par[maxn],deg[maxn],mp[maxn][maxn];
  9. void init()
  10. {
  11.     for(int i=1;i<=50;i++)
  12.         par[i]=i;
  13.     memset(deg,0,sizeof(deg));
  14.     memset(mp,0,sizeof(mp));
  15. }
  16. int find(int x)
  17. {
  18.     if(x==par[x])
  19.         return x;
  20.     else
  21.         return  par[x]=find(par[x]); 
  22. }
  23. void unite(int x,int y)
  24. {
  25.     x=find(x);
  26.     y=find(y);
  27.     if(x!=y)
  28.         par[x]=y;
  29. }
  30. void dfs(int x)
  31. {
  32.     for(int i=1;i<=50;i++)
  33.     {
  34.         if(mp[x][i]>=1)
  35.         {
  36.             mp[x][i]--;
  37.             mp[i][x]--;
  38.             dfs(i);
  39.             printf("%d %d\n",i,x);
  40.         }
  41.     }
  42. }
  43. int main()
  44. {
  45.     int cnt=0;
  46.     scanf("%d",&t);
  47.     while(t--)
  48.     {
  49.         int a,b;
  50.         int mxr=0;
  51.         int hyx=0;
  52.         scanf("%d",&n);
  53.         init();
  54.         for(int i=0;i<n;i++)
  55.         {
  56.             scanf("%d%d",&a,&b);
  57.             mp[a][b]++;
  58.             mp[b][a]++;
  59.             deg[a]++;
  60.             deg[b]++;
  61.             unite(a,b);
  62.         }
  63.         printf("Case #%d\n",++cnt);
  64.         for(int i=1;i<=50;i++)
  65.         {
  66.             if(deg[i]==0) continue;
  67.             if(deg[i]&1) mxr++;
  68.             if(par[i]==i) hyx++;
  69.         }
  70.         if(mxr==0&&hyx==1)
  71.         {
  72.             for(int i=1;i<=50;i++)
  73.                 if(deg[i]!=0)
  74.                     dfs(i);
  75.         }
  76.         else
  77.             printf("some beads may be lost\n");
  78.         printf("\n");
  79.     }
  80.     return 0;
  81. }

B - Guess （UVALive - 4255）

给出一个符号矩阵S，求满足符号矩阵的序列，序列中整数的范围[-10,10]。S(i,j)=ai+...+aj。利用前缀和可以得出sum(i)-sum(j)（>,<,=）0的关系将其前缀和看作结点，已知sum(i)与sum(j)的关系建图，转化为拓扑排序问题，得出满足sum关系的序列最后求出要求序列的每个整数。ps:=0的情况作为度为0的点直接入队列
我们只需要求出满足条件的任意一组解，因为要保证要求序列中每个整数的范围为-10到10，我们sum给值的时候应给[-10,0]或者[0,10]的n个

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8. const int maxn = 15;
  9. int t,n,deg[maxn],sum[maxn];
  10. vector<int>G[maxn];
  11. queue<int>q;
  12. void init()
  13. {
  14.     for(int i=0;i<=n;i++)
  15.     {
  16.         G[i].clear();
  17.     }
  18.     memset(deg,0,sizeof(deg));
  19.     memset(sum,0,sizeof(sum));
  20. }
  21. void bfstop()
  22. {
  23.     int num=0;
  24.     for(int i=0;i<=n;i++)
  25.     {
  26.         if(deg[i]==0){
  27.             q.push(i);
  28.             sum[i]=num;
  29.         }
  30.     }
  31.     while(!q.empty())
  32.     {
  33.         int p=q.front();
  34.         q.pop();
  35.         num++;
  36.         for(int j=0;j<G[p].size();j++)
  37.         {
  38.             --deg[G[p][j]];
  39.             if(deg[G[p][j]]==0)
  40.             {
  41.                 q.push(G[p][j]);
  42.                 sum[G[p][j]]=num;
  43.             }
  44.         }
  45.     }
  46. }
  47. int main()
  48. {
  49.     scanf("%d",&t);
  50.     while(t--)
  51.     {
  52.         scanf("%d",&n);
  53.         init();
  54.         for(int i=0;i<n;i++)
  55.             for(int j=i+1;j<=n;j++)
  56.             {
  57.                 char ch;
  58.                 scanf(" %c",&ch);
  59.                 if(ch=='+'){
  60.                     G[i].push_back(j);
  61.                     deg[j]++;
  62.                 }
  63.                 else if(ch=='-'){
  64.                     G[j].push_back(i);
  65.                     deg[i]++;
  66.                 }
  67.             }
  68.         bfstop();
  69.         for(int i=1;i<n;i++)
  70.             printf("%d ",sum[i]-sum[i-1]);
  71.         printf("%d\n",sum[n]-sum[n-1]);
  72.     }
  73.     return 0;
  74. }

C - Claw Decomposition （UVA - 11396）

题意可以简单概括为给出一个图，问是否能将图分割为若干个爪的图案，且每条边只属于一个爪。
分析出爪中间的点是不会与另外爪的中间点相连的，且爪所连的三个点与另外的爪所连的三个点也是不会相连的。因此满足条件的图是一个二分图，这里我们只需要染色法进行二分图判定即可。爪如下：

        O
        |
        O
       / \
      O   O

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. using namespace std;
  7. const int maxn = 305;
  8. int n,color[maxn];
  9. vector<int>G[maxn];
  10. void init()
  11. {
  12.     for(int i=1;i<=n;i++)
  13.         G[i].clear();
  14. }
  15. bool judge(int v,int c)
  16. {
  17.     color[v]=c;
  18.     for(int i=0;i<G[v].size();i++)
  19.     {
  20.         if(color[G[v][i]]==c) return false;
  21.         if(color[G[v][i]]==0&&!judge(G[v][i],-c)) return false;
  22.     }
  23.     return true;
  24. }
  25. bool solve()
  26. {
  27.     memset(color,0,sizeof(color));
  28.     for(int i=1;i<=n;i++)
  29.     {
  30.         if(color[i]==0)
  31.             if(!judge(i,1))
  32.                 return false;
  33.     }
  34.     return true;
  35. }
  36. int main()
  37. {
  38.     while(cin>>n)
  39.     {
  40.         if(n==0) break;
  41.         int a,b;
  42.         init();
  43.         while(cin>>a>>b)
  44.         {
  45.             if(a==0&&b==0) break;
  46.             G[a].push_back(b);
  47.             G[b].push_back(a);
  48.         }
  49.         if(solve()) printf("YES\n");
  50.         else printf("NO\n");
  51.     }
  52.     return 0;
  53. }

D - Cells (UVALive - 3486)

树多次询问a是否是b的祖先，采用蓝书上时间戳的做法前序后后序遍历存一个pre数组和post数组，祖先的pre数组一定比子结点的pre小，post数组一定比子结点大，我们只需要判断这点即可。ps：这里不能寻常的递归dfs，需要用栈来模拟。因为树深度很大，递归会导致RE

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring> 
  4. #include <algorithm>
  5. #include <vector>
  6. #include <stack>
  7. using namespace std;
  8. const int maxn = 2e7+100;
  9. int t,n,m,dfs_clock;
  10. int pre[maxn],post[maxn];
  11. vector<int>G[maxn];
  12. int vis[maxn];
  13. stack<int>mxr;
  14. void init()
  15. {
  16.     memset(vis,0,sizeof(vis));
  17.     for(int i=0;i<maxn;i++)
  18.         G[i].clear();
  19.     memset(pre,0,sizeof(pre));
  20.     memset(post,0,sizeof(post));
  21. }
  22. void dfs()
  23. {
  24.     mxr.push(0);
  25.     while(!mxr.empty())
  26.     {
  27.         int now=mxr.top();
  28.         if(!vis[now])
  29.         {
  30.             vis[now]=1;
  31.             pre[now]=++dfs_clock;
  32.             for(int i=0;i<G[now].size();i++)
  33.             {
  34.                 int v=G[now][i];
  35.             //  if(!vis[v])
  36.             //      mxr.push(v);
  37.                 if(v<n) mxr.push(v);
  38.                 else{
  39.                     pre[v]=++dfs_clock;
  40.                     post[v]=++dfs_clock;
  41.                 }
  42.             }
  43.         }
  44.         else{
  45.             mxr.pop();
  46.             post[now]=++dfs_clock;
  47.         }
  48.     }
  49. }
  50. int main()
  51. {
  52.     int cnt=0;
  53.     int ok=0;
  54.     scanf("%d",&t);
  55.     while(t--)
  56.     {
  57.         int j=1;
  58.         dfs_clock=0;
  59.         if(ok) printf("\n");ok=1;
  61.         scanf("%d",&n);
  62.         init();
  63.         for(int i=0;i<n;i++)
  64.         {
  65.             int temp;
  66.             scanf("%d",&temp); 
  67.             for(j;temp>0;j++,temp--)
  68.             {
  69.                 G[i].push_back(j);
  70.             }
  71.         }
  72.         dfs();
  73.         scanf("%d",&m);
  74.         printf("Case %d:\n",++cnt);
  75.         for(int i=0;i<m;i++)
  76.         {
  77.             int a,b;
  78.             scanf("%d%d",&a,&b);
  79.             if(pre[a]<pre[b]&&post[a]>post[b])
  80.                 printf("Yes\n");
  81.             else
  82.                 printf("No\n");
  83.         }
  84.         //printf("\n");
  85.     }
  86.     return 0;
  87. }

H - Proving Equivalences (UVALive - 4287)

定理证明，给予几个定理及其证明关系，求至少还需要证明那几个关系才能保证这几个定理之间可以相互推导。题意可以转换为n结点m条边的有向图，添加最少的有向边使得整个图强连通。强连通缩点后统计入度和出度为0的点，ans=max(入度0，出度0)。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. using namespace std;
  7. const int maxn = 20005;
  8. vector<int>G[maxn];
  9. vector<int>rG[maxn];
  10. vector<int>vs;
  11. bool used[maxn];
  12. int cmp[maxn],in[maxn],out[maxn];
  13. int t,n,m;
  14. void init()
  15. {
  16.     memset(in,0,sizeof(in));
  17.     memset(out,0,sizeof(out));
  18.     memset(cmp,0,sizeof(cmp));
  19.     for(int i=1;i<=n;i++)
  20.     {
  21.         G[i].clear();
  22.         rG[i].clear();
  23.     }
  24. }
  25. void dfs(int v)
  26. {
  27.     used[v]=true;
  28.     for(int i=0;i<G[v].size();i++)
  29.     {
  30.         int u=G[v][i];
  31.         if(!used[u])
  32.             dfs(u);
  33.     }
  34.     vs.push_back(v);
  35. }
  36. void rdfs(int v,int k)
  37. {
  38.     used[v]=true;
  39.     cmp[v]=k+1;
  40.     for(int i=0;i<rG[v].size();i++)
  41.     {
  42.         int u=rG[v][i];
  43.         if(!used[u])
  44.             rdfs(u,k);
  45.     }
  46. }
  47. int scc()
  48. {
  49.     memset(used,0,sizeof(used));
  50.     vs.clear();
  51.     for(int i=1;i<=n;i++)
  52.         if(!used[i])
  53.             dfs(i);
  54.     memset(used,0,sizeof(used));
  55.     int k=0;
  56.     for(int i=vs.size()-1;i>=0;i--)
  57.         if(!used[vs[i]])
  58.             rdfs(vs[i],k++);
  59.     return k;
  60. }
  61. int main()
  62. {
  63.     scanf("%d",&t);
  64.     while(t--)
  65.     {
  66.         int a,b,ans,mxr,hyx;
  67.         ans=mxr=hyx=0;
  68.         scanf("%d%d",&n,&m);
  69.         init();
  70.         for(int i=0;i<m;i++)
  71.         {
  72.             scanf("%d%d",&a,&b);
  73.             G[a].push_back(b);
  74.             rG[b].push_back(a);
  75.         }
  76.         int scc_cnt=scc();
  77.         for(int v=1;v<=n;v++)
  78.             for(int j=0;j<G[v].size();j++)
  79.             {
  80.                 int u=G[v][j];
  81.                 if(cmp[u]!=cmp[v]) {//本来就处于强连通的点不考虑
  82.                 //cmp表示缩点后的点的拓扑序
  83.                     in[cmp[u]]++;
  84.                     out[cmp[v]]++;
  85.                 }
  86.             }
  87.         for(int i=1;i<=scc_cnt;i++){
  88.             if(in[i]==0) mxr++;
  89.             if(out[i]==0) hyx++;
  90.         }
  91.         //cout<<mxr<<"*"<<hyx<<endl;
  92.         ans=max(mxr,hyx);
  93.         if(scc_cnt==1)
  94.             ans=0;
  95.         printf("%d\n",ans);
  96.     }
  97.     return 0;
  98. }

J - Now or later (UVALive - 3211)

设早着陆的时间为E，晚着陆的时间为L。有n架飞机着陆， 飞机按实际着陆时间排序，相邻两个着陆时间间隔的最小值要尽量大。输出这个间隔最大值。最小值最大考虑二分答案，设答案为p，即相邻两个时间不小于p。即任意两个飞机的着陆时间不小于p。设布尔变量表示第i架飞机早着陆，根据条件我们可以得到以下几种冲突关系与,与,与,与.于是我们可以列出如下布尔表达式：是一个2-sat问题，要满足题目所给条件即使布尔表达式值为真，我们根据这个表达式建图。根据白书方法建立图，原布尔表达式可以转化为如下表达式：其中表示由a向b连边
利用scc求解(如果和x在同一强连通分量的话则无法令整个布尔表达式为真，且对于每个布尔变量x所在的强连通分量的拓扑序在所在的连通分量之后可以得到x布尔变量为真)是否有满足布尔表达式的一组布尔变量来进行二分。复杂度O()

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. using namespace std;
  7. const int maxn = 4225;
  8. vector<int>G[maxn];
  9. vector<int>rG[maxn];
  10. vector<int>vs;
  11. bool used[maxn];
  12. int cmp[maxn];
  13. int n,early[maxn],late[maxn];
  14. void init()
  15. {
  16.     for(int i=0;i<=n*2;i++)
  17.     {
  18.         G[i].clear();
  19.         rG[i].clear();
  20.     }
  21.     memset(cmp,-1,sizeof(cmp));
  22. }
  23. void add(int from,int to)
  24. {
  25.     G[from].push_back(to);
  26.     rG[to].push_back(from);
  27. }
  28. void dfs(int v)
  29. {
  30.     used[v]=true;
  31.     for(int i=0;i<G[v].size();i++)
  32.     {
  33.         int u=G[v][i];
  34.         if(!used[u])
  35.             dfs(u);
  36.     }
  37.     vs.push_back(v);
  38. }
  39. void rdfs(int v,int k)
  40. {
  41.     used[v]=true;
  42.     cmp[v]=k;
  43.     for(int i=0;i<rG[v].size();i++)
  44.     {
  45.         int u=rG[v][i];
  46.         if(!used[u])
  47.             rdfs(u,k);
  48.     }
  49. }
  50. int scc()
  51. {
  52.     memset(used,0,sizeof(used));
  53.     vs.clear();
  54.     for(int v=0;v<n;v++)
  55.         if(!used[v]) dfs(v);
  56.     memset(used,0,sizeof(used));
  57.     int k=0;
  58.     for(int i=vs.size()-1;i>=0;i--)
  59.         if(!used[vs[i]]) rdfs(vs[i],k++);
  60.     return k;
  61. }
  62. bool judge(int x)
  63. {
  64.     init();
  65.     for(int i=0;i<n;i++)
  66.         for(int j=0;j<i;j++)
  67.         {
  68.             if(abs(early[i]-early[j])<x){
  69.                 add(i,n+j);
  70.                 add(j,n+i);
  71.             }
  72.             if(abs(late[i]-late[j])<x){
  73.                 add(n+i,j);
  74.                 add(n+j,i);
  75.             }
  76.             if(abs(early[i]-late[j])<x){
  77.                 add(i,j);
  78.                 add(n+j,n+i);
  79.             }
  80.             if(abs(late[i]-early[j])<x){
  81.                 add(n+i,n+j);
  82.                 add(j,i);
  83.             }
  84.         }
  85.     scc();
  86.     for(int i=0;i<n;i++)
  87.     {
  88.         if(cmp[i]==cmp[n+i])
  89.             return false;
  90.     }
  91.     return true;
  92. }
  93. int main()
  94. {
  95.     while(scanf("%d",&n)!=EOF)
  96.     {
  97.         init();
  98.         int l,r;
  99.         l=r=0;
  100.         for(int i=0;i<n;i++)
  101.         {
  102.             scanf("%d%d",&early[i],&late[i]);
  103.             r=max(r,max(early[i],late[i]));
  104.         }
  105.         int mxr;
  106.         while(l<=r)
  107.         {
  108.             int m=(l+r)>>1;
  109.         //  cout<<m<<endl;
  110.             if(judge(m))
  111.             {
  112.                 mxr=m;
  113.                 l=m+1;
  114.             }
  115.             else
  116.                 r=m-1;
  117.         }
  118.         printf("%d\n",mxr);
  119.     }
  120.     return 0;
  121. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注