杭电1102
菜鸟求助：杭电1102题。http://acm.hdu.edu.cn/showproblem.php?pid=1102
我做过好多次测试了，好像都没有发现什么问题，但是交了几次都是WA。希望各位大佬能帮帮忙啊。
- C/C++ code
#include <stdio.h>#include<iostream>#include <set>#include <list>using namespace std;//1102int nPath[100][100];int main(){ list<set<int> > setlist; set<int> tmpset,tmpset1; int nVillage,nTmp1,nTmp2; int i,j,nRes=0; bool bTag; list<set<int> >::iterator it; set<int>::iterator itset; while(scanf("%d",&nVillage)!=EOF){ for(i=0;i<nVillage;i++) for(j=0;j<nVillage;j++) scanf("%d",&nPath[i][j]); scanf("%d",&i); for (j=0;j<i;j++) { scanf("%d%d",&nTmp1,&nTmp2); bTag = false; for ( it = setlist.begin();it!=setlist.end();++it) { tmpset = *it; for (itset = tmpset.begin();itset!=tmpset.end();++itset) { if (*itset == nTmp1-1) { it->insert(nTmp2-1); nRes += nPath[*itset][nTmp2-1]; bTag = true; break; } else if ( *itset == nTmp2-1) { it->insert(nTmp1-1); nRes+= nPath[*itset][nTmp1-1]; bTag = true; break; } } if (bTag) { break; } } if (it == setlist.end()) { tmpset.clear(); tmpset.insert(nTmp1-1); tmpset.insert(nTmp2-1); setlist.push_back(tmpset); } } for (i=0;i<nVillage;i++) { bTag = false; for ( it = setlist.begin();it!=setlist.end();++it) { tmpset = *it; for (itset = tmpset.begin();itset!=tmpset.end();++itset) { if (*itset==i) { bTag=true; break; } } if (bTag) { break; } } if (it == setlist.end()) { if (nPath[i][0]!=0) { nTmp1 = nPath[i][0]; } else nTmp1 = nPath[i][1]; for(j=0;j<nVillage;j++) { if (nPath[i][j]!=0 && nPath[i][j]<nTmp1) { nTmp1 = nPath[i][j]; nTmp2 = j; } } //search for j bTag = false; for ( it = setlist.begin();it!=setlist.end();++it) { tmpset = *it; for (itset = tmpset.begin();itset!=tmpset.end();++itset) { if (*itset==nTmp2) { bTag=true; break; } } if (bTag) { break; } } if (bTag==false) {//no tmpset.insert(i); tmpset.insert(nTmp2); nRes += nPath[i][nTmp2]; setlist.push_back(tmpset); } else {//yes it->insert(i); nRes += nPath[nTmp2][i]; } } } while (setlist.size()!=1) { tmpset = setlist.back(); setlist.pop_back(); it = setlist.begin(); set<int>::iterator itset2 = (*it).begin(); itset=tmpset.begin(); nTmp1 = nPath[*itset2][*itset]; //nTmp1 as mimi value for (;itset2!=(*it).end();++itset2) { for (itset=tmpset.begin();itset!=tmpset.end();++itset) { if (nPath[*itset2][*itset]<nTmp1) { nTmp1 = nPath[*itset2][*itset]; } } } nRes += nTmp1; it = setlist.begin(); it->insert(tmpset.begin(),tmpset.end()); } printf("%d\n",nRes); setlist.clear(); nRes = 0; } return 0;}
[解决办法]
这地方插入的时候是不是不需要计算nRes？？
- C/C++ code
if (*itset == nTmp1-1) { it->insert(nTmp2-1); nRes += nPath[*itset][nTmp2-1];//????? bTag = true; break; } else if ( *itset == nTmp2-1) { it->insert(nTmp1-1); nRes+= nPath[*itset][nTmp1-1];//??????? bTag = true; break; }
[解决办法]
自己慢慢调吧，这是必须经历的过程，不然比赛的时候会更痛苦的