社区讨论

问下两种做法的区别

灌水区参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo8ociyx
此快照首次捕获于
2023/10/27 21:54
2 年前
此快照最后确认于
2023/10/27 21:54
2 年前
查看原帖
我的错误代码:
C
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int N=1010;
vector<int> son[N];
ll f[N],js[N],r[N],c[N];
int a,b;
void dfs(int now){
 	for(auto x:son[now]){
		f[x]+=f[now];
		js[x]++;
		if(x!=b&&js[x]==r[x])
		dfs(x);
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	while(m--){
		int x,y;
		cin>>x>>y;
		son[x].push_back(y);
		r[y]++;
		c[x]++;
	}
	cin>>a>>b;
	f[a]=1;
    js[a]++;
	dfs(a);
	cout<<f[b];
	int k=0;
	for(int i=1;i<=n;i++){
		if(c[i]==0&&js[i]) k++;
	}
	if(k==1&&c[b]==0) cout<<" Yes";
    else cout<<" No";
}
正解:
CPP
#include<stdio.h>
int vis[502], path[502],vec[502][502];
int n, m, cnt, a, b;
int DFS(int x) {
    vis[x] = 1;
    if(path[x]) return path[x];
    for(int i=1;i<=n;i++)
        if(vec[x][i])
            path[x] += DFS(i);
    return path[x];
}
int main(){
    int i;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++) {
        scanf("%d %d",&a,&b);
        vec[a][b]=1;
    }
    scanf("%d %d",&a,&b);
    path[b] = 1;
    cnt = DFS(a);
    int flag = 1;
    for(i=1;i<=n;i++) {
        if(vis[i] && !path[i]) {
            flag = 0;
            break;
        }
    }
    printf("%d ",cnt);
    if(!flag)
        printf("No\n");
    else
        printf("Yes\n");
    return 0;
}
我的状态设置就是当前这个从起点到当前这个点方案数,而AC的代码是,从这个点到终点的方案数。这两种状态设置我感觉差不多啊。为什么我会wa两个点呢?

回复

3 条回复,欢迎继续交流。

正在加载回复...