首页 > 搜索 > DFS搜索 > HDU 1824 Let’s go home-DFS-[解题报告] C++
2013
12-23

HDU 1824 Let’s go home-DFS-[解题报告] C++

Let’s go home

问题描述 :

小时候,乡愁是一枚小小的邮票,我在这头,母亲在那头。
                        ―― 余光中

集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每一对队员,如果队员A留下,则队员B必须回家休息下,或者B留下,A回家。由于今年集训队人数突破往年同期最高记录,管理难度相当大,lcy也不知道自己的决定是否可行,所以这个难题就交给你了,呵呵,好处嘛~,免费**漂流一日。

输入:

第一行有两个整数,T和M,1<=T<=1000表示队伍数,1<=M<=5000表示对数。
接下来有T行,每行三个整数,表示一个队的队员编号,第一个队员就是该队队长。
然后有M行,每行两个整数,表示一对队员的编号。
每个队员只属于一个队。队员编号从0开始。

输出:

可行输出yes,否则输出no,以EOF为结束。

样例输入:

1 2
0 1 2
0 1
1 2

2 4
0 1 2
3 4 5
0 3
0 4
1 3
1 4

样例输出:

yes
no

2-sat

#include<iostream>
 #include<vector>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 const int MAX = 20010;
 int n,m,T;
 vector<int>mp[MAX];
 int st[MAX];
 int dfn[MAX],low[MAX];
 int top,btype,tdfn;//btype:连通块的个数
 int belong[MAX];//点属于哪个连通块
 bool ins[MAX];
 void dfs(int s)
 {
     ins[s]=1;
     dfn[s]=low[s]=++tdfn;
     st[++top]=s;
     for(int i=0;i<mp[s].size();i++)
     {
         int t=mp[s][i];
         if(!dfn[t])
         {
             dfs(t);
             if(low[t]<low[s]) low[s]=low[t];
         }
         else if(ins[t]&&dfn[t]<low[s]) low[s]=dfn[t];
     }
     if(dfn[s]==low[s])
     {
         btype++;int t;
         do
         {
             t=st[top--];
             ins[t]=0;
             belong[t]=btype;
         }while(t!=s);
     }
 }
 void scc(int n)
 {
     top=btype=tdfn=0;
     memset(ins,false,sizeof(ins));
     memset(dfn,0,sizeof(dfn));
     for(int i=1;i<=n;i++)
         if(!dfn[i])
             dfs(i);
 }
 int main()
 {
     int x,y,z,a,b;
     while(scanf("%d%d",&T,&m)!=EOF)
     {
         n=3*T;
         for(int i=0;i<=2*n;i++)
             mp[i].clear();
         for(int i=0;i<T;i++)
         {
             scanf("%d%d%d",&x,&y,&z);x++;y++;z++;
             mp[x+n].push_back(y);
             mp[x+n].push_back(z);
             mp[y+n].push_back(x);
             mp[z+n].push_back(x);
         }
         for(int i=0;i<m;i++)
         {
             scanf("%d%d",&a,&b);
             a++;b++;
             mp[a].push_back(b+n);
             mp[b].push_back(a+n);
         }
         scc(2*n);
         int flag=1;
         for(int i=1;i<=n;i++)
         {
             if(belong[i]==belong[i+n])
             {
                 flag=0;
                 break;
             }
         }
         if(flag) printf("yes\n");
         else printf("no\n");
     }
     return 0;
 }

解题报告转自:http://www.cnblogs.com/xuschang-93/archive/2012/03/17/2403393.html


,
  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。