主题:关于ACM图论的问题,请高手帮忙,小生在这儿谢过了
是PKU1130题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1130
这提我的想法是求0到目的点的路径,然后求这条路径上的关键点,求得离目的点最近的关键点,我自己猜测在路径上离目的点最近的那个关键点应该就是所求关键点(不知道对不对 ^^)
然后。。。下面就是偶的代码了,请高手帮忙看看到底是哪里错了,谢谢~
#include<iostream>
using namespace std;
char ch;
int n,key,route[101],fix;
bool adj[101][101],visited[101],flag;
void DFS(int v,int r)
{
int i;
visited[v]=true;
if(v==key){
fix=r;
flag=true;
return;
}
for(i=0;i<n;i++)
if(adj[v][i]==true&&visited[i]==false)
{
route[r]=i;
DFS(i,r+1);
if(flag==true)return;
}
if(i==n)return;
}
void checkDFS(int v){
int i;
visited[v]=true;
if(v==key){
flag=true;
return;
}
for(i=0;i<n;i++)
if(adj[v][i]==true&&visited[i]==false)
{
checkDFS(i);
if(flag==true)return;
}
if(i==n)return;
}
int main()
{
int i,j,r;
while(cin>>n&&n)
{
cin>>key;
getchar();
for(i=0;i<n;i++)
{
visited[i]=false;
for(j=0;j<n;j++)
adj[i][j]=false;
}
while(1)
{
cin.peek();
ch=getchar();
if(!(ch>='0'&&ch<='9'||ch==' '))break;
if(ch>='0'&&ch<='9')
{
cin.putback(ch);
cin>>i>>j;
adj[i][j]=true;
while(1)
{
if(getchar()=='\n')break;
}
}
}
flag=false;
r=1;
route[0]=0;
DFS(0,r);
for(i=fix-2;i>0;i++)//????ET??????????????????????
{
flag=false;
for(j=0;j<n;j++)
visited[j]=false;
visited[route[i]]=true;
checkDFS(0);
if(flag==false)
{
cout<<"Put guards in room "<<route[i]<<"."<<endl;
break;
}
}
if(i==0)cout<<"Put guards in room 0."<<endl;
}
return 0;
}
http://acm.pku.edu.cn/JudgeOnline/problem?id=1130
这提我的想法是求0到目的点的路径,然后求这条路径上的关键点,求得离目的点最近的关键点,我自己猜测在路径上离目的点最近的那个关键点应该就是所求关键点(不知道对不对 ^^)
然后。。。下面就是偶的代码了,请高手帮忙看看到底是哪里错了,谢谢~
#include<iostream>
using namespace std;
char ch;
int n,key,route[101],fix;
bool adj[101][101],visited[101],flag;
void DFS(int v,int r)
{
int i;
visited[v]=true;
if(v==key){
fix=r;
flag=true;
return;
}
for(i=0;i<n;i++)
if(adj[v][i]==true&&visited[i]==false)
{
route[r]=i;
DFS(i,r+1);
if(flag==true)return;
}
if(i==n)return;
}
void checkDFS(int v){
int i;
visited[v]=true;
if(v==key){
flag=true;
return;
}
for(i=0;i<n;i++)
if(adj[v][i]==true&&visited[i]==false)
{
checkDFS(i);
if(flag==true)return;
}
if(i==n)return;
}
int main()
{
int i,j,r;
while(cin>>n&&n)
{
cin>>key;
getchar();
for(i=0;i<n;i++)
{
visited[i]=false;
for(j=0;j<n;j++)
adj[i][j]=false;
}
while(1)
{
cin.peek();
ch=getchar();
if(!(ch>='0'&&ch<='9'||ch==' '))break;
if(ch>='0'&&ch<='9')
{
cin.putback(ch);
cin>>i>>j;
adj[i][j]=true;
while(1)
{
if(getchar()=='\n')break;
}
}
}
flag=false;
r=1;
route[0]=0;
DFS(0,r);
for(i=fix-2;i>0;i++)//????ET??????????????????????
{
flag=false;
for(j=0;j<n;j++)
visited[j]=false;
visited[route[i]]=true;
checkDFS(0);
if(flag==false)
{
cout<<"Put guards in room "<<route[i]<<"."<<endl;
break;
}
}
if(i==0)cout<<"Put guards in room 0."<<endl;
}
return 0;
}