错误答案ACM一个节点太远 [英] Wrong Answer ACM A Node too far
问题描述
我已经写了code的问题的节点过犹不及的问题ID UVA 336，但它给错误的答案任何人可以猜到我在做什么错。下面是我的code。
链接的问题是一个节点太远
此外，如果有人能告诉我什么是对得到一个错误的答案的常见原因，是有什么办法，我们知道，这对我们的输入程序创建的问题。
的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;列表＆gt;
＃包括＆LT;地图＆GT;
无符号整型caseID = 0;
结构边缘;
结构节点{
节点（）：编号（0），成本（0），颜色（假）中，加入（假）{}
INT ID;
INT费用;
布尔色;
布尔补充;
的std ::名单＆LT;边缘*＆GT;的边缘;
};
结构边缘{
边缘（）：目标（0）{}
节点*目的地;
};
无效make_graph（unsigned int类型的SourceID，无符号整型destinationid，
的std ::地图＆LT; INT，节点*＆GT; ＆功放; MYMAP，INT和放大器; totalNodes）{
节点*来源= 0;
节点*目的= 0;
的std ::地图＆LT; INT，节点*＆GT;：迭代它= mymap.find（的SourceID）;
如果（它== mymap.end（））{
来源=新节点;
++ totalNodes;
源 - ＆GT; ID =的SourceID;
mymap.insert（标准::对＆LT; INT，节点*＆GT;（的SourceID，源））;
}
其他{
来源= IT-＆gt;第二个;
}
如果（的SourceID == destinationid）{
返回;
}
它= mymap.find（destinationid）;
如果（它== mymap.end（））{
++ totalNodes;
目标=新节点;
destination-＆GT; ID = destinationid;
mymap.insert（标准::对＆LT; INT，节点*＆GT;（destinationid，目的地））;
}
其他{
目的地= IT-＆gt;第二个;
}
边缘* E =新的边缘;
E-＆GT;目标=目标;
源 - ＆GT; edges.push_back（E）;
E =新的边缘;
E-＆GT;目标=来源;
destination-＆GT; edges.push_back（E）;
}
无效delete_graph（性病::地图＆LT; INT，节点*＆GT;＆安培; MYMAP）{
的std ::地图＆LT; INT，节点*＆GT;：迭代它= mymap.begin（）;
为（;！它= mymap.end（））{
节点* N =它 - ＆gt;第二个;
如果（！n）的{
继续;
}
的std ::名单＆LT;边缘*＆GT;：迭代myEdge = IT-＆GT;二线＆GT; edges.begin（）;
而（myEdge =正 - ＆GT;！edges.end（））{
边缘* E = * myEdge;
如果（E）{
E-＆GT;目标= 0;
删除电子邮件;
E = 0;
}
++ myEdge;
}
删除N;
N = 0;
++它;
性病::法院＆LT;＆LT;的std :: ENDL;
}
}
无效calc_nodes（int值，节点* N，无符号整型和放大器; nodesCount，诠释prevCost）{
如果（N-＆GT;！加入）{
正＆GT;成本= ++ prevCost;
如果（N-＆GT;成本==值）{
++ nodesCount;
正＆GT;添加= TRUE;
返回;
}
++ nodesCount;
正＆GT;添加= TRUE;
}其他{
正＆GT;成本= ++ prevCost;
}
的std ::名单＆LT;边缘*＆GT;：迭代它= N＆GT; edges.begin（）;
而（它= N＆GT;！edges.end（））{
边缘* E = *（它）;
如果（E-＆GT; destination-＆GT;彩色）{
++它;
继续;
}
正＆GT;彩色= TRUE;
E-＆GT; destination-＆GT;彩色= TRUE;
calc_nodes（值，E＆GT;的目标，nodesCount，正＆GT;成本）;
++它;
}
}
无效clearGraph（性病::地图＆LT; INT，节点*＆GT;＆安培; MYMAP）{
的std ::地图＆LT; INT，节点*＆GT;：迭代它= mymap.begin（）;
而（它！= mymap.end（））{
IT-＆GT;二线＆GT;添加= FALSE;
IT-＆GT;二线＆GT;彩色= FALSE;
++它;
}
}
无效calc_nodes_aux（INT totalNodes，性病::地图＆LT; INT，节点*＆GT;＆安培; MYMAP）{
unsigned int类型TTL = 0;
节点*来源= 0;
unsigned int类型的sourceID = 0;
无符号整型nodesCount = 0;
而（真）{
给std :: cin＆GT;＆GT;的sourceID＆GT;＆GT; TTL;
如果（的sourceID == 0安培;＆安培; TTL == 0）{
打破;
}
的std ::地图＆LT; INT，节点*＆GT;：迭代它= mymap.find（的sourceID）;
来源= IT-＆gt;第二个;
如果（源和放大器;＆安培; TTL大于0）{
nodesCount = 0;
clearGraph（MYMAP）;
calc_nodes（TTL，源，nodesCount，-1）;
如果（caseID大于0）{
性病::法院＆LT;＆LT;的std :: ENDL;
}
性病::法院＆LT;＆LT; 案例＆LT;＆LT; ++ caseID＆其中;＆所述;：＆其中;＆所述; totalNodes - nodesCount＆其中;＆其中;
节点从节点不可达＆LT;＆LT;的sourceID＆LT;＆LT; 与TTL =＆LT;＆LT; TTL＆其中;＆所述;。;
}
}
}
诠释的main（）{
无符号整型边缘= 0;
unsigned int类型的sourceID = 0;
无符号整型destinationId = 0;
而（真）{
给std :: cin＆GT;＆GT;的边缘;
如果（边== 0）{
打破;
}
的std ::地图＆LT; INT，节点*＆GT; MYMAP;
INT totalNodes = 0;
为（unsigned int类型I = 0; I＆LT;边缘; ++ I）{
给std :: cin＆GT;＆GT;的sourceID＆GT;＆GT; destinationId;
make_graph（的sourceID，destinationId，MYMAP，totalNodes）;
}
calc_nodes_aux（totalNodes，MYMAP）;
delete_graph（MYMAP）;
}
返回0;
}
您code是极其复杂，给定的任务，你甚至不通过示例测试！请注意，在（几乎全部）的在线判定你被要求产生一个输出，它是相同的字节方式作为预期之一。您产值约10个额外的换行字符后的第一个测试用例，甚至，如果你的code另有纠正，这将导致错误的答案。
下面是关于如何解决这方面的问题更省力两种方法：
所有你需要做的是建立节点图，然后运行广度优先搜索< /一>从在查询的节点。此后数有初始节点大于给定的阈值（TTL）。
的最短距离的所有节点作为节点的数量是非常小的（最多30个），另一种解决方案将是运行的弗洛伊德沃肖尔</A>算法。该解决方案将是更短，但不会为更大的约束工作。
这两种方式都可以轻松地安装在不到50行。
如何找到哪个测试你是否有WA就是尽量产生随机图形和模拟任意两个节点之间的包的动作，并将结果与一个由你的程序中找到比较的一种方法。总是产生小例子！在这种情况下，我相信最多5个节点的更多的则是足够的。
第二条本办法，我一般preFER是生成图表的手，用手重新计算预期的答案。尽量覆盖尽可能多的边缘情况越好（在网络中的单个节点中，所有节点是可到达的，TTL为0等）。 在网上的法官只有少数提供选项，看看哪些情况下是你的code对失败和UVA是不是其中之一。这样做是为了一个目的 - 它迫使你去尝试和调试程序在您自己。同样在ACM总决赛没有人会告诉你，你是失败的情况。
I have written code for the problem "A Node too far" problem id uva 336. But it is giving wrong answer can any one guess what i am doing wrong. Below is my code.
The link to the problem is A Node too far
Also if someone can tell me what is the common reasons for getting a wrong answer and is there any way that we know that against which input our program is creating problems.
#include <iostream>
#include <vector>
#include <list>
#include <map>
unsigned int caseID = 0;
struct Edge;
struct Node{
Node():id(0),cost(0),color(false),added(false){}
int id;
int cost;
bool color;
bool added;
std::list<Edge *>edges;
};
struct Edge{
Edge():destination(0){}
Node *destination;
};
void make_graph(unsigned int sourceid,unsigned int destinationid,
std::map<int, Node*> &mymap, int &totalNodes){
Node *source = 0;
Node *destination = 0;
std::map<int, Node*>::iterator it = mymap.find(sourceid);
if(it == mymap.end()){
source = new Node;
++ totalNodes;
source->id = sourceid;
mymap.insert(std::pair<int,Node*> (sourceid,source));
}
else{
source = it->second;
}
if(sourceid == destinationid){
return;
}
it = mymap.find(destinationid);
if(it == mymap.end()){
++totalNodes;
destination = new Node;
destination->id= destinationid;
mymap.insert(std::pair<int,Node*> (destinationid,destination));
}
else{
destination = it->second;
}
Edge *e = new Edge;
e->destination = destination;
source->edges.push_back(e);
e = new Edge;
e->destination = source;
destination->edges.push_back(e);
}
void delete_graph(std::map<int, Node*> &mymap){
std::map<int,Node*>::iterator it = mymap.begin();
for(;it != mymap.end(); ){
Node *n = it->second;
if(!n){
continue;
}
std::list<Edge *>::iterator myEdge = it->second->edges.begin();
while(myEdge != n->edges.end()){
Edge *e = *myEdge;
if(e){
e->destination = 0;
delete e;
e = 0;
}
++myEdge;
}
delete n;
n = 0;
++it;
std::cout << std::endl;
}
}
void calc_nodes(int value, Node *n, unsigned int &nodesCount, int prevCost){
if(!n->added){
n->cost = ++prevCost;
if(n->cost == value){
++nodesCount;
n->added = true;
return;
}
++nodesCount;
n->added = true;
}else{
n->cost = ++prevCost;
}
std::list<Edge *>::iterator it = n->edges.begin();
while(it != n->edges.end()){
Edge *e = *(it);
if(e->destination->color){
++it;
continue;
}
n->color = true;
e->destination->color = true;
calc_nodes(value,e->destination,nodesCount,n->cost);
++it;
}
}
void clearGraph(std::map<int, Node *>& mymap ){
std::map<int, Node *>::iterator it = mymap.begin();
while(it != mymap.end()){
it->second->added = false;
it->second->color = false;
++it;
}
}
void calc_nodes_aux(int totalNodes,std::map<int,Node *> &mymap){
unsigned int TTL = 0;
Node *source = 0;
unsigned int sourceId = 0;
unsigned int nodesCount = 0;
while(true){
std::cin >> sourceId >>TTL;
if(sourceId == 0 && TTL == 0){
break;
}
std::map<int,Node *>::iterator it = mymap.find(sourceId);
source = it->second;
if(source && TTL > 0){
nodesCount = 0;
clearGraph(mymap);
calc_nodes(TTL,source,nodesCount, -1);
if(caseID > 0){
std::cout <<std::endl;
}
std::cout << "Case "<< ++caseID<<": " <<totalNodes - nodesCount <<
" nodes not reachable from node " <<sourceId << " with TTL = " << TTL<<".";
}
}
}
int main(){
unsigned int edges = 0;
unsigned int sourceId = 0;
unsigned int destinationId = 0;
while(true){
std::cin >>edges;
if(edges == 0){
break;
}
std::map<int,Node*>mymap;
int totalNodes = 0;
for(unsigned int i = 0; i < edges; ++i ){
std::cin >> sourceId >> destinationId;
make_graph(sourceId,destinationId,mymap,totalNodes);
}
calc_nodes_aux(totalNodes,mymap);
delete_graph(mymap);
}
return 0;
}
Your code is extremely complicated for the task given and you do not even pass the example test! Please note that in (almost all) online judges you are required to produce an output that is the same byte-wise as the expected one. You output about 10 additional newline characters after the first test case and even if your code is otherwise correct this will result in wrong answer.
Here are two approaches on how to solve this particular problem with less effort:
All you need to do is to build the graph of nodes and then run a breadth first search from the node in the query. After that count all nodes that have their shortest distance to the initial node greater then the given threshold(the TTL).
As the number of nodes is really small(up to 30), an alternative solution would be to run a Floyd Warshall algorithm. This solution will be even shorter but will not work for much greater constraints.
Both approaches could easily fit in less then 50 lines.
One approach on how to find which test do you have WA is to try generating random graphs and simulate the movement of the packages between any two nodes and compare the result with the one found by your program. Always generate small examples! In this case I believe up to 5 nodes is more then enough.
Second approach, which I generally prefer is to generate graphs by hand and compute the expected answer again by hand. Try to cover as many edge cases as possible(single node in the network, all nodes are reachable, TTL is 0 and so on). In the online judges only a few offer the option to see which case is your code failing on and UVA is not one of them. This is done for a purpose - it forces you to try and debug your program on your own. Also on ACM finals no one is going to tell you the case that you are failing.
这篇关于错误答案ACM一个节点太远的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
