• 向德荣寓言:农夫、青蛙与苍蝇(原创首发) 2019-05-19
  • 杭州教师史记体评语引热议 网友直呼有才、用心 2019-05-13
  • 晋世绘——黄河新闻网 2019-05-13
  • 河北:举报环境违法行为最高可奖励5万元 2019-05-05
  • 魏占军的专栏作者中国国家地理网 2019-05-02
  • 回复@老老保老张工:那边有个铁环,比较适合伪高工玩…… 2019-05-02
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-04-20
  • 让中国高铁领跑世界——我国高铁装备业唯一女总工程师梁建英 2019-04-19
  • eHub发布“鲁班”智能营销云 重塑智能时代的商业变革 2019-04-18
  • 拜博口腔医疗集团创始人、董事长黎昌仁获第十二届人民企业社会责任奖年度人物奖 2019-04-18
  • 巴川中学王苗:留守儿童长大了 2019-04-15
  • 真正学进去 积极讲出来 扎实做起来市委常委部门分别召开会议传达学习全国两会精神 2019-04-15
  • 实拍武汉万人“父母相亲会”  现场“摆摊”征婚 2019-04-13
  • 丸子-热门标签-华商生活 2019-04-13
  • 房奴!房奴!亚历山大幸福吗? 2019-04-06
  • 欢迎来到蒟蒻mqd的博客

    coderfoces D. Gourmet choice

     

    D. Gourmet choice

    time limit per test
    2 seconds
    memory limit per test
    256 megabytes
     
    题目链接:
    Discribe

    广东十一选5一定牛 www.aavbg.com Mr. Apple, a gourmet, works as editor-in-chief of a gastronomic periodical. He travels around the world, tasting new delights of famous chefs from the most fashionable restaurants. Mr. Apple has his own signature method of review  — in each restaurant Mr. Apple orders two sets of dishes on two different days. All the dishes are different, because Mr. Apple doesn't like to eat the same food. For each pair of dishes from different days he remembers exactly which was better, or that they were of the same quality. After this the gourmet evaluates each dish with a positive integer.

    Once, during a revision of a restaurant of Celtic medieval cuisine named «Poisson», that serves chestnut soup with fir, warm soda bread, spicy lemon pie and other folk food, Mr. Apple was very pleasantly surprised the gourmet with its variety of menu, and hence ordered too much. Now he's confused about evaluating dishes.

    The gourmet tasted a set of n

    dishes on the first day and a set of m dishes on the second day. He made a table a of size n×m, in which he described his impressions. If, according to the expert, dish i from the first set was better than dish j from the second set, then aij is equal to ">", in the opposite case aij is equal to "<". Dishes also may be equally good, in this case aij

    is "=".

    Now Mr. Apple wants you to help him to evaluate every dish. Since Mr. Apple is very strict, he will evaluate the dishes so that the maximal number used is as small as possible. But Mr. Apple also is very fair, so he never evaluates the dishes so that it goes against his feelings. In other words, if aij

    is "<", then the number assigned to dish i from the first set should be less than the number of dish j from the second set, if aij is ">", then it should be greater, and finally if aij

    is "=", then the numbers should be the same.

    Help Mr. Apple to evaluate each dish from both sets so that it is consistent with his feelings, or determine that this is impossible.

    Input

    The first line contains integers n

    and m (1n,m1000

    ) — the number of dishes in both days.

    Each of the next n

    lines contains a string of m symbols. The j-th symbol on i-th line is aij

    . All strings consist only of "<", ">" and "=".

    Output

    The first line of output should contain "Yes", if it's possible to do a correct evaluation for all the dishes, or "No" otherwise.

    If case an answer exist, on the second line print n

    integers — evaluations of dishes from the first set, and on the third line print m

    integers — evaluations of dishes from the second set.

    Examples
    Input
    3 4
    >>>>
    >>>>
    >>>>
    
    Output
    Yes
    2 2 2 
    1 1 1 1 
    
    Input
    3 3
    >>>
    <<<
    >>>
    
    Output
    Yes
    3 1 3 
    2 2 2 
    
    Input
    3 2
    ==
    =<
    ==
    
    Output
    No
    
    Note

    In the first sample, all dishes of the first day are better than dishes of the second day. So, the highest score will be 2

    , for all dishes of the first day.

    In the third sample, the table is contradictory — there is no possible evaluation of the dishes that satisfies it.

     

    题意

    有两个点集分别有n个点和m个点,告诉你第一个集合里的所有点的权值和第二个集合里的所有点的权值的大小关系。

    问是否能给每个点赋一个值,使得满足题目所给的大小关系,如果可以,输出任意一组合法解。

     

    题解:

    对于任意两个点ai和bj,如果ai<bj则,连一条从j到i的单向边,问题即为每个点的最长路。

    如果相等,我们缩点即可。如果有环则说明无解。

    具体步骤:

    先缩点,再判环,我直接tarjan求环,然后再在DAG上dfs求最长路即可。

    Debug:

    1.一开始先不管相等的边,判环再缩点,导致可能缩点之后又有新的环产生。

    2.一看n<1000,平时做多了n和边是一个数量级的题目,于是边只开了10000,还以为够了,真是惯性思维惹的祸,还是太菜了。

     

    代码:

     

     1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 2000050
     4 char road[2000][2000];
     5 int n,m,fa[N],f[N],ans[N];
     6 bool flag=0;
     7 struct Edge{int from,to,s;}edges[N<<1],edges2[N<<2];
     8 int tot,last[N];
     9 template<typename T>void read(T&x)
    10 {
    11   int k=0;char c=getchar();
    12   x=0;
    13   while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
    14   if(c==EOF)exit(0);
    15   while(isdigit(c))x=x*10+c-'0',c=getchar();
    16   x=k?-x:x;
    17 }
    18 void read_char(char &c)
    19 {while((c=getchar())!='<'&&c!='>'&&c!='='&&c!=EOF);}
    20 int gf(int x)
    21 {
    22   if (x==fa[x])return x;
    23   fa[x]=gf(fa[x]);
    24   return fa[x];
    25 }
    26 void AddEdge(int x,int y)
    27 {
    28   edges[++tot]=Edge{x,y,last[x]};
    29   last[x]=tot;
    30 }
    31 int low[N],dfn[N],sk[N],at_sk[N],top,Time;
    32 void tarjan(int x)
    33 {
    34   dfn[x]=++Time;
    35   low[x]=Time;
    36   sk[++top]=x;
    37   at_sk[x]=1;
    38   f[x]=1;
    39   for(int i=last[x];i;i=edges[i].s)
    40     {
    41       Edge &e=edges[i];
    42       if (gf(x)==gf(e.to))flag=true;
    43       if (!f[e.to])tarjan(e.to);
    44       if (at_sk[e.to])low[x]=min(low[x],low[e.to]);
    45     }
    46   if (sk[top]!=x)flag=true;
    47   if (low[x]==dfn[x])
    48     {
    49       while(sk[top+1]!=x&&top)
    50     at_sk[sk[top--]]=0;
    51     }
    52 }
    53 void dfs(int x)
    54 {
    55   f[x]=1;
    56   ans[x]=0;
    57   for(int i=last[x];i;i=edges[i].s)
    58     {
    59       Edge &e=edges[i];
    60       if(!ans[e.to]&&!f[e.to])dfs(e.to);
    61       ans[x]=max(ans[x],ans[e.to]);
    62     }
    63   ans[x]++;
    64 }
    65 int main()
    66 {
    67 #ifndef ONLINE_JUDGE
    68   freopen("aa.in","r",stdin);
    69 #endif
    70   read(n);read(m);
    71   char c;
    72   for(int i=1;i<=n+m+n;i++)fa[i]=i;
    73   for(int i=1;i<=n;i++)
    74     for(int j=1;j<=m;j++)
    75       {
    76     read_char(c);
    77     //if (c=='<')AddEdge(j+n,i);
    78     //if (c=='>')AddEdge(i,j+n);
    79     road[i][j]=c;
    80     if (c=='=')fa[gf(i)]=gf(j+n);
    81       }
    82   for(int i=1;i<=n;i++)
    83     for(int j=1;j<=m;j++)
    84       if (road[i][j]=='<')AddEdge(gf(j+n),gf(i));
    85       else if (road[i][j]=='>')AddEdge(gf(i),gf(j+n));
    86   
    87   for(int i=1;i<=n+m;i++) if(!f[gf(i)]&&!flag)tarjan(gf(i));
    88   if (flag)
    89     {
    90       printf("No");
    91       return 0;
    92     }
    93   printf("Yes\n");
    94   memset(f,0,sizeof(f));
    95   for(int i=1;i<=n+m;i++) if (!f[gf(i)]) dfs(gf(i));
    96   for(int i=1;i<=n;i++) printf("%d ",ans[gf(i)]);
    97   putchar('\n');
    98   for(int i=1;i<=m;i++) printf("%d ",ans[gf(i+n)]);
    99 }
    View Code

     

    posted @ 2019-04-20 01:59 mmqqdd 阅读(...) 评论(...) 编辑 收藏
  • 向德荣寓言:农夫、青蛙与苍蝇(原创首发) 2019-05-19
  • 杭州教师史记体评语引热议 网友直呼有才、用心 2019-05-13
  • 晋世绘——黄河新闻网 2019-05-13
  • 河北:举报环境违法行为最高可奖励5万元 2019-05-05
  • 魏占军的专栏作者中国国家地理网 2019-05-02
  • 回复@老老保老张工:那边有个铁环,比较适合伪高工玩…… 2019-05-02
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-04-20
  • 让中国高铁领跑世界——我国高铁装备业唯一女总工程师梁建英 2019-04-19
  • eHub发布“鲁班”智能营销云 重塑智能时代的商业变革 2019-04-18
  • 拜博口腔医疗集团创始人、董事长黎昌仁获第十二届人民企业社会责任奖年度人物奖 2019-04-18
  • 巴川中学王苗:留守儿童长大了 2019-04-15
  • 真正学进去 积极讲出来 扎实做起来市委常委部门分别召开会议传达学习全国两会精神 2019-04-15
  • 实拍武汉万人“父母相亲会”  现场“摆摊”征婚 2019-04-13
  • 丸子-热门标签-华商生活 2019-04-13
  • 房奴!房奴!亚历山大幸福吗? 2019-04-06