POJ3687---Labeling Balls-阿里云开发者社区

POJ3687---Labeling Balls

2022-12-08 64

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： POJ3687---Labeling Balls

题目描述

Windy 有 N 个不同重量的球，从 1 个单位到 N 个单位。现在，他尝试以 1 到 N 的方式标记它们：

没有两个球共享相同的标签。

标签满足几个约束条件，例如“标有 a 的球比标有 b 的球轻”。

你能帮助windy找到解决办法吗？

输入

输入的第一行是测试用例的数量。每个测试用例的第一行包含两个整数，N (1 ≤ N ≤ 200) 和 M (0 ≤ M ≤ 40,000)。接下来的 M 行每行包含两个整数 a 和 b，表示标有 a 的球必须比标有 b 的球轻。 (1 ≤ a, b ≤ N) 每个测试用例前有一个空行。

输入样例:

输出样例

思路: 本题的意思是,给出N个标签球,标签球之间的大小关系已经给出,我们要做的是按照重量的大小给每一个标签球进行标号,重量大的标号也就大,如果某一次标号中多个球都满足标号的条件,那么按照球号大的进行先标号,标号也是1–N. 如果中间存在了环也就无法进行标号,那么解就不存在.

样例:

在样例中,先对3号求进行标号:label[3] = 5,然后删除3号球的两条边,这时1,2号都可进行标号,那么由于2号求号更大,所以先进行label[2] = 4,之后1,4号也可进行标号,同样先label[4] = 3,然后label[1] = 2,label[5] = 1; 在标号过程中,我们是按照出度为0的球进行标号.

由于题中没说明,则可能会出现重边,在构建时,如果边已经存在了,入度就不需要进行+1了.否则会出现,有的顶点其实没有入度边了,但入度数组中该大小还不为0.

解题思路:

建立原图的逆向图,这样在每次进行标号时,我们是依据入度为0进行搞的.由于中间可能出现多个球都可进行标号,所以我们不能再使用栈了,我们改用使用一个for(int i = n; i >= 1; i--) 在这个过程中我们先要寻找入度为0的球且是最大标号的那个,然后进行标号,从而进行下一轮.如果不能找到,则说明该图中存在环,结束即可. 对于每一次循环都会进行一次标号.

采用正向图,但处理的时候是根据出度为0的点进行标号的,同时该点的所有出度进行-1,之后的思路和上个思路相同.

参考代码

#include<iostream>
#include<string.h>
using namespace std;
const int maxn = 210;
int map[maxn][maxn],label[maxn],in[maxn],n,m,t,flag,T;
void TopoSort(){
  flag = 0;
  for(int i = n; i >= 1; i--){//采用循环来进行标号.  
    //寻找入度为0的最大标号的球.
    t = 0;//用于存找到的入度为0的最大编号. 
    for(int j = n; j>=1; j--){//从标号最大开始找,找到的第一个即是最大的那个. 
      if(!in[j]){
        t = j;
        break; 
      }
    } 
    if(!t){//如果没有找到则说明有环. 
      flag = 1;
      break;
    }
    in[t] = -1;//入度改变,防止影响下一次入度为0节点的寻找. 
    label[t] = i;//进行标号
    for(int j = 1; j <= n; j++){//该点所有临界点的入度进行-1 
      if(map[t][j]){
        in[j]--;
      }
    } 
  }
} 
int main()
{
  int u,v;
  cin>>T;
  while(T--){
    //初始化
    memset(map,0,sizeof(map));
    memset(label,0,sizeof(label));
    memset(in,0,sizeof(in)); 
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
      cin>>u>>v;
      if(!map[v][u]) {//如果已经读入过了就不再进行读入,防止重边影响Topo排序. 
        map[v][u] = 1;
        in[u]++; 
      }   
    }
    TopoSort();
    if(flag){//有环 
      cout<<"-1"<<endl;
    }else{
      for(int i = 1; i <= n-1; i++){//标号成功则进行输出. 
        cout<<label[i]<<" ";
      }
      cout<<label[n]<<endl;
    } 
  }
  return 0;
}

POJ3687---Labeling Balls

题目描述

输入

输入样例:

输出样例

参考代码

热门文章

最新文章

相关电子书