开心小屋

本文主要是介绍开心小屋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
Kc来到开心小屋。开心小屋是用来提升心情的。在这个小屋中有n个房间，一些房间之间有门连通。从房间i到达房间j，心情值可以加上-10000<=Cij<=10000，当然Cij可能是负的。现在kc失恋了，所以他想要知道他是否可以在这个小屋中无限地增加他的心情值，也就是无限地绕着一个环走？

请帮kc求出最小的环需要经过的房间数，来使他的心情无限增加。

输入
第一行给出，1<=n<=300，1<=m<=5000。分别表示房间数及门的数量。

接下来m行，每行四个数：i,j,Cij,Cji
输出
输出文件包括一行，及最小的环需要经过的房间数。

保证不会出现自环及重边。
输入样例
4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3
输出样例
4
样例解释：
1—>3—>4–>2–>1为最小的符合题意的环长度为4.
说明
Data Constraint
对30%的数据，n<=10;
对60%的数据,，n<=100;
对100%的数据，n<=300;

.
.
.
.
.
.
分析
题意：求有向图中，所有正权环长度的最小值

深搜——暴力出奇迹
从每个位置开始搜环
那么考虑剪枝：
1.若当前所搜过的屋子个数超过了先前找的答案，return。
2.若从起点到当前位置，它的和已经成了负数，return。

第一个容易理解。而第二个，由于我们要求正权环，所以负值不行
(“负值”拼音五个字母，所以五子不行，手动狗头)
对于一个环，若其和为正，说明在这环中，无论从哪个点出发，回来都会是正的，那么就必然存在一个点，从其出发走的这个环，过程中的值必为正(在这个满足要求的环中，由于我们正好是从每一个点开始搜，所以我们仍能找到另一个点来走这个环，同时使得过程中，和不为负值)。
如：88 5 -90 1 2 这个环
所以就算将“过程中和为负数”的枝剪去，对答案无影响

.
.
.
.
.
.
程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;int n,m,wz,ans=2147483647,a[310][310];
bool v[310];void dfs(int x,int dep,int sum)
{if (dep>ans||sum<0) return;if (x==wz&&dep!=0){if (sum>0) ans=min(ans,dep); return;}for (int i=1;i<=n;i++)if (a[x][i]<=10000&&!v[i]){v[i]=true;dfs(i,dep+1,sum+a[x][i]);v[i]=false;}return;
}int main()
{scanf("%d%d",&n,&m);memset(a,0x3f,sizeof(a));for (int i=1;i<=m;i++){int u,v,x,y;scanf("%d%d%d%d",&u,&v,&x,&y);a[u][v]=x;a[v][u]=y;}for (int i=1;i<=n;i++){wz=i;dfs(i,0,0);}printf("%d",ans);return 0;
}

这篇关于开心小屋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---