本文共 1288 字，大约阅读时间需要 4 分钟。

题目描述

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

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

输入

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

接下来m行，每行四个数：i,j,Cij,Cji

输出

输出文件包括一行，及最小的环需要经过的房间数。

保证不会出现自环及重边。

样例输入

4 41 2 -10 31 3 1 -102 4 -10 -13 4 0 -3

样例输出

4样例解释：1--->3--->4-->2-->1为最小的符合题意的环长度为4.

解

DFS+剪枝。

从一个点开始寻找从它开始从它结束的环。

剪枝:

我们只寻找以出发点开始结束的环，所以——

代码

#include
   
    bool B[10001];int l[10001];int n, m, u, v, uv, vu, t, beginn, ans = 3000;struct asdf{    int to,zz,next;} a[1000001];void dfs(int d, int deep, int sum){    if(sum < 0 || deep > ans) return;  //剪枝 if(d == beginn && deep != 0){    //回到原点  if(sum > 0) ans = deep;  //正环，sum=0的时候不算  return; } for(int i = l[d]; i; i = a[i].next)  //dfs if(B[a[i].to] == 0){     B[a[i].to] = 1;  dfs(a[i].to, deep+1, sum+a[i].zz);  B[a[i].to] = 0; }}int main(){    scanf("%d%d",&n,&m); for(int i = 1; i <= m; ++i){     scanf("%d%d%d%d",&u,&v,&uv,&vu);  if(uv+vu>0){      printf("2");   return 0;  }  a[++t] = (asdf){   v,uv,l[u]}; l[u] = t;  a[++t] = (asdf){   u,vu,l[v]}; l[v] = t; } for(int i = 1; i <= n; ++i){     //从每一个点开始      beginn = i;      dfs(i,0,0); } printf("%d",ans);}