• “两学一做”在山西——黄河新闻网 2019-07-13
  • 内地生报读香港高校本科人数持续下跌 2019-07-13
  • 【学习时刻】人民大学王义桅:金砖合作的“自信”与“自觉” 2019-07-12
  • 女子请“私家侦探”被骗3万 警方循线捣毁诈骗团伙 2019-07-11
  • 【学习时刻】北交大马院院长韩振峰:高校思想政治工作必须牢牢把握三大根本问题 2019-07-11
  • 全国“非遗”保护工作先进名单公布 2019-07-01
  • 紫光阁中共中央国家机关工作委员会 2019-06-25
  • 杭州控烟令修改草案拟允许室内设吸烟区,控烟专家:跌破眼镜 2019-06-25
  • 挪用近30万报纸征订款赌博 河南一报社聘用制干部获刑 2019-06-23
  • 2016年,有1145家上市公司大小非减持了3600亿元,还有210名上市公司高管减持了1400亿元。IPO已成了造就成千上万个十亿、百亿富豪的捷径, 2019-06-21
  • 专家“把脉”中国电影市场:提升品质方能逆袭 2019-06-21
  • “善款资助副局长儿子留学”真相须尽快落地 2019-06-19
  • 21岁女护士失联2天后确认遇害 嫌疑人为其前男友 2019-06-19
  • 中国地质公园名录旅行地中国国家地理网 2019-06-13
  • 玄关运用有四大原则 用的好才能财旺挡煞聚财 ——凤凰网房产 2019-06-10
  • 欢迎来到蒟蒻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-07-13
  • 内地生报读香港高校本科人数持续下跌 2019-07-13
  • 【学习时刻】人民大学王义桅:金砖合作的“自信”与“自觉” 2019-07-12
  • 女子请“私家侦探”被骗3万 警方循线捣毁诈骗团伙 2019-07-11
  • 【学习时刻】北交大马院院长韩振峰:高校思想政治工作必须牢牢把握三大根本问题 2019-07-11
  • 全国“非遗”保护工作先进名单公布 2019-07-01
  • 紫光阁中共中央国家机关工作委员会 2019-06-25
  • 杭州控烟令修改草案拟允许室内设吸烟区,控烟专家:跌破眼镜 2019-06-25
  • 挪用近30万报纸征订款赌博 河南一报社聘用制干部获刑 2019-06-23
  • 2016年,有1145家上市公司大小非减持了3600亿元,还有210名上市公司高管减持了1400亿元。IPO已成了造就成千上万个十亿、百亿富豪的捷径, 2019-06-21
  • 专家“把脉”中国电影市场:提升品质方能逆袭 2019-06-21
  • “善款资助副局长儿子留学”真相须尽快落地 2019-06-19
  • 21岁女护士失联2天后确认遇害 嫌疑人为其前男友 2019-06-19
  • 中国地质公园名录旅行地中国国家地理网 2019-06-13
  • 玄关运用有四大原则 用的好才能财旺挡煞聚财 ——凤凰网房产 2019-06-10
  • 体彩快乐扑克走势 浙江体彩20选5开奖查询 七星彩17046期规律 广东11选5盘古人工计划 今日青海快三 曾道人点特玄机黑白图 浙江风采网南粤36选7走势图 可爱mm沙滩排球 贵州快3开奖结果走试图 宁夏11选5宁夏助手 波色公式规律 四川时时彩官网 188排球比分 18选7共有多少等级奖 秒速时时彩开奖网站