三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 【poj 3385】【模板】负环 -> 正文阅读
 

[C++]【poj 3385】【模板】负环

【poj 3385】【模板】负环 题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
输入输出格式
输入格式:
第一行一个正整数T表示数据组数,对于每组数据:
第一行两个正整数N M,表示图有N个顶点,M条边
接下来M行,每行三个整数a b w,表示a->b有一条权值为w的边(若w<0则为单向,否则双向)
输出格式:
共T行。对于每组数据,存在负环则输出一行"YE5"(不含引号),否则输出一行"N0"(不含引号)。
输入输出样例
输入样例#1:

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出样例#1:

N0
YE5

说明
N,M,|w|≤200 000;1≤a,b≤N;T≤10 建议复制输出格式中的字符串。
此题普通Bellman-Ford或BFS-SPFA会TLE
题解
注意有两个个坑点,当然我都被坑到了。//脸红
1.无向边和双向边的问题,所以边数会需要乘二。
2.输出的是YE'5'和N'0'(均不含单引号)。
1.利用BellmanFord判负环。
  如果不存在负环的话,那么最多经过N - 1次迭代就可以得到最短路。因为形成最短路最多N - 1个节点(起点不算),但是如果存在了负环,那么就可以一直迭代,最短路会越来越小。可以利用这个性质来判断是否存在负环。(此题会挂)


 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 200005
 6 using namespace std;
 7 int read(){
 8     int x=0,f=1;char ch=getchar();
 9     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int t,n,m,d[maxn],cnt;
14 struct node{
15     int from,to,cost;
16 }e[maxn*2];
17 bool BF(int sta){
18     for(int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
19     d[sta]=0;
20     for(int i=1;i<n;i++){
21         bool flag=false;
22         for(int j=1;j<=cnt-1;j++){
23             if(d[e[j].to]>(d[e[j].from]+e[j].cost)){
24                 flag=true;
25                 d[e[j].to]=d[e[j].from]+e[j].cost;
26             }
27         }
28         if(!flag) break;
29     }
30     for(int i=1;i<=cnt-1;i++)
31         if(d[e[i].to]>(d[e[i].from]+e[i].cost))
32             return false;
33     return true;
34 }
35 int main(){
36     t=read();
37     while(t--){
38         cnt=1;
39         memset(e,0,sizeof(e));
40         n=read(),m=read();
41         for(int i=1;i<=m;i++){
42             int u=read(),v=read(),w=read();
43             if(w>=0){
44                 e[cnt].to=v;e[cnt].from=u;e[cnt++].cost=w;
45                 e[cnt].to=u;e[cnt].from=v;e[cnt++].cost=w;
46             }
47             else if(w<0)e[cnt].to=v;e[cnt].from=u;e[cnt++].cost=w;
48         }
49         if(BF(1)) printf("N0\n");
50         else printf("YE5\n");
51     }
52     return 0;
53 }

2.利用spfa判负环。
  1.记录松弛次数,超过n则证明存在负环。(会TLE)


 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 200005
 7 #define inf 0x3f3f3f3f
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int t,n,m,d[maxn],cnt,inq[maxn],last[maxn],times[maxn];
16 struct node{
17     int next,to,cost;
18 }e[maxn*2];
19 void add(int u,int v,int w){
20     e[++cnt].to=v;e[cnt].next=last[u];e[cnt].cost=w;last[u]=cnt;
21 }
22 bool spfa(int s,int t){
23     queue<int> q;
24     q.push(s);
25     d[s]=0;inq[s]=1;times[s]++;
26     while(!q.empty()){
27         int u=q.front();q.pop();
28         inq[u]=0;
29         for(int i=last[u];i;i=e[i].next){
30             if(d[e[i].to]>d[u]+e[i].cost){
31                 d[e[i].to]=d[u]+e[i].cost;
32                 if(!inq[e[i].to]){
33                     inq[e[i].to]=1;
34                     q.push(e[i].to);
35                     times[e[i].to]++;
36                     if(times[e[i].to]>n) return false;
37                 }
38             }
39         }
40     }
41     return true;
42 }
43 int main(){
44     t=read();
45     while(t--){
46         n=read(),m=read();
47         cnt=0;
48         memset(last,0,sizeof(last));
49         memset(inq,0,sizeof(inq));
50         memset(d,inf,sizeof(d));
51         memset(times,0,sizeof(times));
52         for(int i=1;i<=m;i++){
53             int u=read(),v=read(),w=read();
54             if(w>=0) add(u,v,w),add(v,u,w);
55             else if(w<0) add(u,v,w);
56         }
57         if(spfa(1,n)) printf("N0\n");
58         else printf("YE5\n");
59     }
60     return 0;
61 }

  2.后来想了想,因为我们只需要判断负环,相当于我们需要找到一条权值和为负的回路,那不妨使距离数组d初始化为0。这样处理后,第一次拓展只会拓展到与起点相连边权为负的边。那么我们就分别枚举所有的点作为起点,如果已经找到一个负环就不再继续枚举。根据SPFA,我们找到的负环一定包含当前枚举的这个点(因为这个点出现了两次)。(AC)


 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define maxn 200005
 7 #define inf 0x3f3f3f3f
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 bool flag;
16 int t,n,m,d[maxn],cnt,inq[maxn],last[maxn],vis[maxn];
17 struct node{
18     int next,to,cost;
19 }e[maxn*2];
20 void add(int u,int v,int w){
21     e[++cnt].to=v;e[cnt].next=last[u];e[cnt].cost=w;last[u]=cnt;
22 }
23 void dfs_spfa(int s){
24     if(flag)  return ;
25     vis[s]=true;
26     for(int i=last[s];i;i=e[i].next){
27         if(flag) return ;
28         int v=e[i].to;
29         if(d[s]+e[i].cost<d[v]){
30             d[v]=d[s]+e[i].cost;
31             if(vis[v]){
32                 flag=true;
33                 return ;
34             }
35             else dfs_spfa(v);
36         }
37     }
38     vis[s]=false;
39 }
40 int main(){
41     t=read();
42     while(t--){
43         n=read(),m=read();
44         cnt=0;
45         memset(last,0,sizeof(last));
46         memset(d,0,sizeof(d));
47         memset(vis,0,sizeof(vis));
48         for(int i=1;i<=m;i++){
49             int u=read(),v=read(),w=read();
50             if(w>=0) add(u,v,w),add(v,u,w);
51             else if(w<0) add(u,v,w);
52         }
53         flag=false;
54         for(int i=1;i<=n;i++){
55             dfs_spfa(i);
56             if(flag) break;
57         }
58         if(flag) printf("YE5\n");
59         else printf("N0\n");
60     }
61     return 0;
62 }

  C++ 最新文章
10.21测试
4927 线段树练习5
Eff C++ 笔记1
codevs4919 线段树练习4
洛谷P1720 月落乌啼算钱
POJ 27777 count color (线段树——带lazy
extern "C" 用法解析
Windows 环境搭建cocos2dx 3.x Eclipse的环
设计模式学习笔记
1355: [Baltic2009]Radio Transmission
上一篇文章           查看所有文章
加:2017-10-11 23:23:59  更:2017-10-11 23:24:22 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年10日历
2017-10-22 7:13:09
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库