Tag: 九度OJ

Categories
不学无术

九度OJ 题目1448：Legal or Not

题目描述：
ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many “holy cows” like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost “master”, and Lost will have a nice “prentice”. By and by, there are many pairs of “master and prentice”. But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?We all know a master can have many prentices and a prentice may have a lot of masters too, it’s legal. Nevertheless，some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian’s master and, at the same time, 3xian is HH’s master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not. Please note that the “master and prentice” relation is transitive. It means that if A is B’s master ans B is C’s master, then A is C’s master.
输入：
The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y’s master and y is x’s prentice. The input is terminated by N = 0.TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,…, N-1). We use their numbers instead of their names.
输出：
For each test case, print in one line the judgement of the messy relationship.If it is legal, output “YES”, otherwise “NO”.
样例输入：
3 2
0 1
1 2
2 2
0 1
1 0
0 0
样例输出：
YES
NO

===========================================
不合法情况的发生原因：有向图中有圈
怎么确定有向图中有没有圈：拓扑排序，有圈的排不出的~
怎么进行拓扑排序：
找入读为0的节点n，删掉节点及节点的关联边，然后n节点放到拓扑排序的队列中
具体还是看代码
===========================================

#include
using namespace std;
int findZeroInDegree(int **adjMatrix, int N, bool *visited)
{
//在邻接矩阵中找【入】度为0的节点。
for(int col=0; col> N && N!=0)
{
int M;
cin >> M;
int **adjMatrix = new int*[N];
bool *visited = new bool[N];
int i;
for(i=0; i> x >> y;
adjMatrix[x][y] = 1;
}
///
int count = 0;
int nextNode = findZeroInDegree(adjMatrix, N, visited);
while(nextNode != -1)
{
removeRelatedEdge(adjMatrix, nextNode, N);
nextNode = findZeroInDegree(adjMatrix, N, visited);
count ++;
}
///
if(count == N)
cout << "YES" << endl; else cout << "NO" << endl; ///Delete for(i=0; i

Categories
不学无术

九度OJ 题目1012：畅通工程

题目描述：
    某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
输入：
    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
输出：
    对每个测试用例，在1行里输出最少还需要建设的道路数目。
样例输入：
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
样例输出：
1
2
998

==============================
这个题目，概念上就是求非连通图里面联通子图的数量…道路嘛就是再加几条边能把各个联通子图连起来~
做法的话，用并查集弄吧~
并查集最简单的玩法就是，弄一个亲爹数组，数组里面存指向自己亲爹的指针，没爹的就是根了…
统计有几个没爹的就是统计有多少联通子图
==============================

#include
using namespace std;
int findRoot(int *parentAry, int currIndex)
{
if(parentAry[currIndex] == -1)
return currIndex; //没爹了，currIndex就是爹
else
{
int rootIndex = findRoot(parentAry, parentAry[currIndex]);
//压缩路径
parentAry[currIndex] = rootIndex;
return rootIndex;
}
}
int main()
{
int N;
while(cin >> N && N!=0)
{
int M;
cin >> M;
int *parentAry = new int[N];
int i;
for(i=0; i> x >> y;
x--; y--;
int parentX = findRoot(parentAry, x);
int parentY = findRoot(parentAry, y);
if(parentX != parentY)
{
//不在一个集合中，合并！
parentAry[parentX] = parentY; //将X当前的根挂在Y的根上
}
}
int count = 0;
for(i=0; i

Categories
不学无术

九度OJ 题目1109：连通图

题目描述：
    给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。
输入：
    每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。如果 n 为 0 表示输入结束。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。
输出：
    对于每组输入数据，如果所有顶点都是连通的，输出”YES”，否则输出”NO”。
样例输入：
4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0
样例输出：
NO
YES

====================================
这两天弄几道简单的做做…
这个是图联通的检测，可以用DFS或者BFS做，其实函数给个int返回值，返回这个节点标记了几个，这样后面main函数里面就不用再遍历一次visited数组了~
发现以前申请的空间都不delete的，现在感觉就像便便了没擦屁股一样…
调试出来第一遍发现怎么都不对，后来细看发现申请出来的二维数组没有初始化…噗
呐，如果是BFS的话，按照数据结构书上讲，用队列来搞，不用递归就行了。把本层访问到的节点塞到工作队列中就行..
====================================

#include
using namespace std;
void DFS( bool **connMatrix, bool *visited, int N, int c)
{
//connMatrix: 连通矩阵
//visited ：是否访问
//N : 节点数
//c : 当前节点编号
visited[c] = true; //Mark current node as visited
int i;
for(i=0; i> N && N != 0)
{
cin >> M;
//Create matrix and visited
bool **connMat = new bool*[N];
bool *visited = new bool[N];
int i;
for(i=0; i> x >> y;
x--;
y--; //Subscript starts from 1 in the input
connMat[x][y] = true;
connMat[y][x] = true;
}
//Manipulate
DFS(connMat, visited, N, 0);
bool flag = true;
for(i=0; i

Categories
不学无术

九度OJ 题目1172：哈夫曼树

题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出：
输出权值。
样例输入：
5
1 2 2 5 9
样例输出：
37

=================================
吐槽:VC6里面智能提示好像到while语句之类的循环里面就会失效，然后就只能盲打..Orz…
=================================

#include
#include
#include
using namespace std;
struct Node
{
int val;
Node *parent;
Node()
{
parent = NULL;
}
int getHeight()
{
int h = 0;
Node *p = parent;
while(p != NULL)
{
h++;
p = p->parent;
}
return h;
}
};
bool compare(Node *x, Node *y)
{
return x->val > y->val;
}
int main()
{
int N;
while(cin >> N)
{
vector workingSet;
Node *nodes = new Node[N]; //Primitive Nodes
int i;
for(i=0; i> nodes[i].val;
workingSet.push_back(&nodes[i]);
}
///
while(workingSet.size() > 1)
{
sort(workingSet.begin(), workingSet.end(), compare);
Node *small1 = workingSet.back();
workingSet.pop_back();
Node *small2 = workingSet.back();
workingSet.pop_back();
//Combine
Node *combined = new Node;
combined->val = small1->val + small2->val;
small1->parent = combined;
small2->parent = combined;
workingSet.push_back(combined);
}
//output
int sum = 0;
for(i=0; i

Categories
不学无术

九度OJ 题目1190：大整数排序

题目描述：
对N个长度最长可达到1000的数进行排序。
输入：
输入第一行为一个整数N，(1<=N<=100)。
接下来的N行每行有一个数，数的长度范围为1<=len<=1000。
每个数都是一个正数，并且保证不包含前缀零。
输出：
可能有多组测试数据，对于每组数据，将给出的N个数从小到大进行排序，输出排序后的结果，每个数占一行。
样例输入：
3
11111111111111111111111111111
2222222222222222222222222222222222
33333333
样例输出：
33333333
11111111111111111111111111111
2222222222222222222222222222222222

==========================================

#include
#include
#include
using namespace std;
struct BigInt
{
char data[1001]; // 高位在前，低位在后
};
int compare(const void *pA, const void *pB)
{
BigInt *a = (BigInt *)pA;
BigInt *b = (BigInt *)pB;
int len_a = strlen(a->data);
int len_b = strlen(b->data);
if(len_a < len_b) return -1; else if(len_a > len_b)
return 1;
else
{
int i;
for(i = 0; idata[i] != b->data[i])
return a->data[i] - b->data[i];
}
}
return 0;
}
int main()
{
char input[1001];
int N;
while(cin >> N)
{
BigInt *bigInts = new BigInt[N];
int i;
for(i=0; i> input;
strcpy(bigInts[i].data, input);
}
qsort(bigInts, N, sizeof(BigInt), compare);
for(i=0; i