社区讨论
全家福,WA,TLE,MLE
P2296[NOIP 2014 提高组] 寻找道路参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi4ebypy
- 此快照首次捕获于
- 2025/11/18 17:53 4 个月前
- 此快照最后确认于
- 2025/11/18 17:53 4 个月前
CPP
#include<iostream>
using namespace std;
int a[10001][10001],n,m,ans=1,start,end,chu[10001],min1=999999,flag[10001],biao[10001],num;
void judge(int k)
{
if (k==end) return;
else if (chu[k]==0&&k!=end)
{
for (int i=1;i<=n;i++)
{
if (a[i][k]==1)
{
chu[i]--,a[i][k]=0;
for (int j=1;j<=n;j++)
{
if (a[j][i]==1) chu[j]--,a[j][i]=0;
if (a[i][j]==1) chu[i]--,a[i][j]=0;
}
}
}
return;
}
int i;
for (i=1;i<=n;i++)
{
if (a[k][i]==1&&biao[i]==0) biao[i]=1,judge(i);
}
}
void read()
{
int i,j,x,y;
cin>>n>>m;
for (i=1;i<=m;i++)
cin>>x>>y,a[x][y]=1,chu[x]++;
cin>>start>>end;
for (i=1;i<=n;i++)
{
for (int l=1;l<=n;l++)
biao[l]=0;
judge(i);
cout<<endl;
}
}
void dfs(int k,int ans)
{
int i;
if (ans<min1&&k==end)
{
min1=ans;
return;
}
else if (k==end&&ans>=min1) return ;
for (i=1;i<=n;i++)
{
if (a[k][i]&&flag[i]==0) flag[i]=1,num++,dfs(i,ans+1);
}
}
int main()
{
read();
dfs(start,ans);
cout<<num;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...