社区讨论

全家福,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 条回复,欢迎继续交流。

正在加载回复...