毛豆

用户名：liuyt

访问量：16842

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

能量项链解题思想
浏览：228

大数除法例题解析
浏览：538

map的使用方法
浏览：775

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

bfs与dfs实战解题

　　作者: 毛豆　　　　发表时间：2019-10-01 23:25:40 浏览：665　|　评论：0　

燕大食堂为了改善学生伙食，新开了一条小吃街。这里共有n个摊位，剁椒鱼头、水煮肉片、牛奶冻、红烧狮子头……各种各样的美食数不胜数，散发着诱人的香气。 SueJane和swoky非常开心地走进小吃街。这里有一条神奇的规定，如果能回答出所有小吃的价格，就可以获得免单的优惠。swoky贿赂了入口处卖可乐鸡翅的大妈，得知了标号为1的摊位（可乐鸡翅）的价格为a_1。此后SueJane和swoky每走到一个摊位，都可以获得一条信息，内容为这个摊位的小吃与另外某一个摊位的差价。现在SueJane和swoky大快朵颐之后来到出口处，发现由于她们吃了太多美食，钱不够了qwq。因此，她们必须猜出所有小吃的价格来获得免单的优惠。你这位神犇能帮她们的忙吗？

输入格式:
输入第一行为三个正整数，为n,m,a_1，分别表示摊位个数、SueJane和swoky获得的信息条数、摊位1的价格。 接下来共有m行，每行包括三个整数x,y,z，表示x摊位的价格比y摊位贵z元钱。

输出格式:
第一行为一个字符串，“QWQ”表示你太强了觉得这个问题非常简单，可以帮她们解决；“QAQ”表示由于SueJane和swoky太蠢了收集到了错误的信息或者没有收集全信息，你对此爱莫能助。 如果第一行输出了"QWQ"，那么接下来输出n行每行一个整数，分别表示1～n个摊位的小吃价格。

输入样例1:
在这里给出一组输入。例如：

5 5 10
1 2 3
4 3 2
1 3 2
3 5 1
4 5 3
输出样例1:
在这里给出相应的输出。例如：

QWQ
10
7
8
10
7
输入样例2:
在这里给出一组输入。例如：

5 5 10
1 2 3
4 3 2
1 3 2
3 5 1
4 5 2
输出样例2:
在这里给出相应的输出。例如：

QAQ
输入样例3:
在这里给出一组输入。例如：

5 4 10
4 3 2
1 3 2
3 5 1
4 5 2
输出样例3:
在这里给出相应的输出。例如：

QAQ
样例说明
样例1中，信息之间不存在矛盾的情况且可以得出所有答案。
样例2中，第2，4，5条信息互相矛盾。
样例3中，给出的信息不能够计算出第2个摊位的小吃价格。
数据范围及约定
    //本人水平菜
    
    //第一份代码  有bug的dfs
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+100;
    int e[N],ne[N],h[N],w[N],idx;//链式前向星 
    int n,m,first;
    int ves[N];//每个点存的权值  ves[1]=first; 
    bool reach[N];
    int tag;
    void add(int a,int b,int c)
    {
    	e[idx]=b;
    	w[idx]=c;
    	ne[idx]=h[a];
    	h[a]=idx++;
    }
    bool dfs(int u)
    {
    	
    	reach[u]=true;
    	for(int i=h[u];i!=-1;i=ne[i])
    	{
    		int j=e[i];
    		
    	  if(reach[j]&&ves[u]+w[i]==ves[j])
    		{
    			continue;
    		}
    		else if(ves[j]==0)
    		{
    			ves[j]=ves[u]+w[i];
    			bool t=dfs(j);
    			if(t==false)
    			{
    				return t;
    			}
    		}
    		else{
    		  return false;
    		}
    	}
    	return true;
    	
    }
    int main()
    {
    	cin>>n>>m>>first;
    	memset(h,-1,sizeof h);
    	memset(ves,0,sizeof ves);//每个点多大权值 
    	for(int i=0;i<m;i++)
    	{
    		int a,b,c;
    		cin>>a>>b>>c;
    		add(a,b,-c);
    		add(b,a,c);
    	}
    	ves[1]=first;//
    	int t=dfs(1); 
    	if(t)
    	{
    		cout<<"QWQ"<<endl;
    		for(int i=1;i<=n;i++)
    		{
    			cout<<ves[i]<<endl;
    		}
    		return 0;
    	}
    	cout<<"QAQ";
     }

//第二份代码
    //可以ac的bfs
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long  ll;
    typedef pair<int,int> pa;
    const int MAXN=1e5+5;
     
    vector <pa> a[MAXN];
    int n , m ,b;
    bool reach[MAXN];
    int p[MAXN];
     
    bool bfs(int i){
        queue<int>q;
        q.push(i);
        reach[i]=true;
        int k=1;
        while(!q.empty()){
            int j=q.front(),len=a[j].size();
            q.pop();
            for(int i=0;i<len;i++){
                int f=a[j][i].first,s=a[j][i].second;
                if(p[f]&&p[j]!=p[f]+s)return  false;
                if(p[f]==0) p[f]=p[j]-s;
                if(!reach[f]){
                    reach[f]=true;
                    k++;
                    q.push(f);
                }
            }
        }
        if(k!=n)return false;
        return true;
    }
     
    int main()
    {
        int v1,v2,w;
        scanf("%d%d%d",&n,&m,&b);
        p[1]=b;
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&v1,&v2,&w);
            a[v1].emplace_back(pa(v2,w));
            a[v2].emplace_back(pa(v1,-w));
        }
        if(bfs(1)){
            printf("QWQ\n");
            for(int i=1;i<=n;i++)printf("%d\n",p[i]);
        } else printf("QAQ");
    }

//第三份经过大佬指点后可以ac的dfs代码
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+100;
    int e[N],ne[N],h[N],w[N],idx;//链式前向星 
    int n,m,first;
    long long ves[N];//每个点存的权值  ves[1]=first; 
    bool reach[N];
    int tag;
    void add(int a,int b,int c)
    {
    	e[idx]=b;
    	w[idx]=c;
    	ne[idx]=h[a];
    	h[a]=idx++;
    }
     
    bool dfs(int u)
    {
    	
    	reach[u]=true;
    	for(int i=h[u];i!=-1;i=ne[i])
    	{
    		int j=e[i];
    		
    	  if(reach[j]&&ves[u]+w[i]==ves[j])
    		{
    			continue;
    		}
    		else if(ves[j]==0)
    		{
    			ves[j]=ves[u]+w[i];
    			bool t=dfs(j);
    			if(t==false)
    			{
    				return t;
    			}
    		}
    		else{
    		  return false;
    		}
    	}
    	return true;
    	
    }
     
    int main()
    {
    	cin>>n>>m>>first;
    	memset(h,-1,sizeof h);
    	memset(ves,0,sizeof ves);//每个点多大权值 
    	for(int i=0;i<m;i++)
    	{
    		int a,b,c;
    		cin>>a>>b>>c;
    		add(a,b,-c);
    		add(b,a,c);
    	}
    	ves[1]=first;//
    	int t=dfs(1); 
    	if(t)
    	{
    		for(int i=1;i<=n;i++)
    		{
    			if(!reach[i])
    			{
    				cout<<"QAQ";
    				return 0;
    			}
    		}
    		cout<<"QWQ"<<endl;
    		for(int i=1;i<=n;i++)
    		{
    			cout<<ves[i]<<endl;
    		}
    		return 0;
    	}
    	cout<<"QAQ";
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-计负均正（C语言代码）

printf基础练习2 （C语言代码）

不容易系列2 （C语言代码）

bfs与dfs实战解题

评论区

精彩推荐

The 3n + 1 problem （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

上车人数（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言考试练习题_排列（C++代码）

2^k进制数（C++代码）使用递归方法

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蛇行矩阵（C语言代码）

WU-输出九九乘法表（C++代码）

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-计负均正 （C语言代码）

printf基础练习2 （C语言代码）

不容易系列2 （C语言代码）

bfs与dfs实战解题

评论区

精彩推荐

The 3n + 1 problem （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

上车人数 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言考试练习题_排列 （C++代码）

2^k进制数 （C++代码）使用递归方法

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蛇行矩阵 （C语言代码）

WU-输出九九乘法表 （C++代码）

C二级辅导-计负均正（C语言代码）

　　评论区

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

上车人数（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言考试练习题_排列（C++代码）

2^k进制数（C++代码）使用递归方法

蛇行矩阵（C语言代码）

WU-输出九九乘法表（C++代码）