【题目链接】

点击打开链接

【算法】

差分约束系统,SPFA判负环

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 1010
#define MAXM 200010 struct Edge
{
int to,w,nxt;
} e[MAXM];
int i,n,m,a,b,c,tot;
int dis[MAXN],head[MAXN];
char opt[]; inline void add(int u,int v,int w)
{
tot++;
e[tot] = (Edge){v,w,head[u]};
head[u] = tot;
}
inline bool spfa()
{
int i,cur,v,w;
queue<int> q;
static bool inq[MAXN];
static int cnt[MAXN];
for (i = ; i <= n; i++)
{
dis[i] = ;
q.push(i);
inq[i] = true;
cnt[i] = ;
}
while (!q.empty())
{
cur = q.front();
q.pop();
inq[cur] = false;
for (i = head[cur]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (dis[cur] + w > dis[v])
{
dis[v] = dis[cur] + w;
if (!inq[v])
{
inq[v] = true;
cnt[v]++;
if (cnt[v] > n) return false;
q.push(v);
}
}
}
}
return true;
}
int main()
{ while (scanf("%d",&n) != EOF && n)
{
tot = ;
for (i = ; i <= n; i++) head[i] = ;
scanf("%d",&m);
while (m--)
{
scanf("%s",&opt);
if (strcmp(opt,"P") == )
{
scanf("%d%d%d",&a,&b,&c);
add(b,a,c);
add(a,b,-c);
} else
{
scanf("%d%d",&a,&b);
add(b,a,);
}
}
if (spfa()) printf("Reliable\n");
else printf("Unreliable\n");
} return ; }

最新文章

  1. android需知小细节
  2. Codeforces 706 C. Hard problem (dp)
  3. 【Xamarin挖墙脚系列:现有IPhone/IPad 设备尺寸】
  4. ECMA5.1中Object.seal()和Object.freeze()的区别
  5. poj 1132
  6. centos6.7下 编译安装MySQL5.7
  7. Jquery 中each循环嵌套的使用示例教程
  8. 使用Visual Studio 2010 创建简单的Silverlight应用程序
  9. [TroubleShooting]&amp;#39;trn\bak&amp;#39; is incorrectly formed. SQL Server cannot process this media family.
  10. 基于C#的Appium自动化测试框架(Ⅰ):程序结构
  11. 全景拍摄,全景视频拍摄,全景VR拍摄,VR全景拍摄,360全景图片拍摄
  12. Oracle两个数据库联合查询,使用Oracle DBLink
  13. redis &amp; memcache 性能比较
  14. 自动化测试基础篇--Selenium单选框(Radio)复选框(CheckBox)
  15. url请求老是有 之前的部分url
  16. 使用python读取yaml文件
  17. 利用函数或映射进行数据转换 (map)
  18. lintcode-511-交换链表当中两个节点
  19. SSH电力项目一 搭建Hibernate框架
  20. Emmet使用方法

热门文章

  1. Go:错误处理
  2. html页面加载初始化方法
  3. Python爬虫例子(笔记,不适合参考,愿意看的可以看看)
  4. Qt笔记——连接第三方库&amp;用libZPlay库获取音频文件的艺术家、专辑等信息
  5. Android SwipeSelector
  6. Online IDE &amp; Public URLs &amp; turbo
  7. ELK pipeline
  8. Codeforces Round #457 (Div. 2) B
  9. hdu - 1068 Girls and Boys (二分图最大独立集+拆点)
  10. Codeforces Round #343 (Div. 2)【A,B水题】