回 帖 发 新 帖 刷新版面

主题:关于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;
}

回复列表 (共1个回复)

沙发

胡邹两句
那个题目我看了

问题应该是这样
给定了网络拓扑 以及每条边的方向(单向)
求关键点 条件应该满足
1 该点是通过起始点到达终点的必经点
2 所有到达终点的路径都必须经过该点
同时满足以上两个条件的离终点最近的点就是所求的点了

如果按你说的 在路径上离目的点最近的那个关键点应该就是所求关键点
那你会不会选点5和点6?

你的程序我不会看 不会C++

我来回复

您尚未登录,请登录后再回复。点此登录或注册