题意:总共有n+m个点,每一个点都有一个val,给出一个n*m的矩阵,矩阵中第i行第j列的为=,表示 i 点 和 j+n个点的值相等,<表示i 点比j+n个点的值小,> 刚好相反

要求用最少的值给每一个点确定一个val,满足如上那个矩阵,如果不存在输出Yes

存在输出每一个点的val

题解:大小关系可以转化为有向边,等于关系则是利用并查集进行缩点,因此value的分配可以利用拓扑排序来解决,如果存在环说明无解

具体细节看代码

int fa[maxn];

int Find(int x){
return fa[x]==x?x:fa[x]=Find(fa[x]);
} int n,m; char sym[1005][1005]; int id[maxn]; int head[maxn],ver[maxm],nex[maxm],tot; void inline AddEdge(int x,int y){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
} int d[maxn]; bool vis[maxn]; int main(){
cin>>n>>m;
for(int i=1;i<=n+m;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>sym[i][j];
if(sym[i][j]=='=') {
int px=Find(i),py=Find(j+n);
if(px!=py){
fa[px]=py;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(sym[i][j]=='<') {
AddEdge(Find(i),Find(j+n));
d[Find(j+n)]++;
}
else if(sym[i][j]=='>'){
AddEdge(Find(j+n),Find(i));
d[Find(i)]++;
}
}
}
queue<int> q;
for(int i=1;i<=n+m;i++)
if(!d[Find(i)]) q.push(Find(i));
while(q.size()){
int x=q.front();q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=ver[i];
d[y]--;
id[y]=max(id[y],id[x]+1);
if(!d[y]) {
q.push(y);
}
}
}
for(int i=1;i<=n+m;i++)
if(d[Find(i)]) {
cout<<"No";
return 0;
}
puts("Yes");
for(int i=1;i<=n;i++)
cout<<id[Find(i)]+1<<' ';
cout<<endl;
for(int i=1;i<=m;i++)
cout<<id[Find(i+n)]+1<<' ';
cout<<endl;
}

  

最新文章

  1. AutoMapper(七)
  2. WAV文件头相关资料
  3. Effective C++ -----条款06:若不想使用编译器自动生成的函数,就该明确拒绝
  4. VS中两个常用辅助工具
  5. bzoj4216 Pig
  6. ios特性访问器方法(setter和getter)
  7. linux进程管理之开机启动
  8. Winodws安装系统时,通过安装磁盘进行分区
  9. 人见人爱a*b 杭电2035
  10. DOM动态添加表格
  11. linux源码安装nodejs
  12. SQL分页存储过程(不支持多表联合查询,不支持多字段排序)
  13. Codeforces 777A Shell Game
  14. docker run 之后执行多条命令
  15. sqlserver 导入excel
  16. [转]list的交集,差集,并集
  17. git常用操作命令使用说明
  18. BZOJ 1040: [ZJOI2008]骑士(基环树dp)
  19. iOS设置圆角的四种方法
  20. Yarn执行流程

热门文章

  1. Dubbo Cluster集群那点你不知道的事。
  2. 隐马尔可夫(HMM)/感知机/条件随机场(CRF)----词性标注
  3. Hibernate(五)
  4. 6.场景4:使用VRRP(L3HA)和Open vSwitch提供高可用性
  5. ASP.NET Core on K8S 入门学习系列文章目录
  6. BZOJ 1046 [HAOI2007]上升序列(LIS + 贪心)
  7. 微信小程序中的图表构建
  8. c语言小游戏-三子棋的完成
  9. Github搜索技巧-如何使用github找到自己感兴趣的项目(转载)
  10. step1:准备歌词之《前端开发是个啥》