NOIP模拟赛虫洞

【题目描述】

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1..N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

【输入格式】

* Line 1: 一个整数 F, 表示农场个数。

* Line 1 of each farm: 三个整数 N, M, W。

* Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。

* Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。

【输出格式】

* Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"。

【样例输入】

3 3 1

1 2 2

1 3 4

2 3 1

3 1 3

3 2 1

1 2 3

2 3 4

3 1 8

【样例输出】

YES

floyd判负环：好像会超时2个点

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int INF=10000;
 6 const int MAXN=501;
 7 
 8 int f,n,m,w;
 9 int Dist[MAXN][MAXN],Graph[MAXN][MAXN];
10 int minn;
11 
12 void floyd()
13 {
14     memcpy(Graph,Dist,sizeof(Dist));
15     for(int k=1;k<=n;k++)
16     {
17         for(int i=1;i<k;i++)
18             for(int j=i+1;j<k;j++)
19                 minn=min(minn,Dist[i][j]+Graph[j][k]+Graph[k][i]);
20         if(minn<0) return;
21         for(int i=1;i<=n;i++)
22             for(int j=1;j<=n;j++)
23             {
24                 int temp=Dist[i][k]+Dist[k][j];
25                 if(temp<Dist[i][j])
26                     Dist[i][j]=temp;
27             }
28     }
29 }
30 
31 inline void Init()
32 {
33     minn=INF;
34     for(int i=1;i<=n;i++)
35         for(int j=1;j<=n;j++)
36         {
37             if(i==j) Dist[i][j]=0;
38             else Dist[i][j]=INF;
39         }
40 }
41 
42 int main()
43 {
44     scanf("%d",&f);
45     for(int Loop=1;Loop<=f;Loop++)
46     {
47         scanf("%d %d %d",&n,&m,&w);
48         Init();
49         for(int i=1;i<=m;i++)
50         {
51             int s,e,t;
52             scanf("%d %d %d",&s,&e,&t);
53             Dist[s][e]=Dist[e][s]=min(Dist[s][e],t);
54         }
55         for(int i=1;i<=w;i++)
56         {
57             int s,e,t;
58             scanf("%d %d %d",&s,&e,&t);
59             Dist[s][e]=min(Dist[s][e],-t);
60         }
61         floyd();
62         if(minn<0) printf("YES
");
63         else printf("NO
");
64     }
65     return 0;
66 }

spfa判负环：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int INF=10000;
 6 const int MAXN=501;
 7 
 8 struct Edge
 9 {
10     int to,w,next;
11 }E[100001];
12 int node=0,head[505];
13 
14 int f,n,m,w;
15 
16 int Dist[501];
17 bool vis[501];
18 bool flag;
19 
20 void insert(int u,int v,int w)
21 {
22     node++;
23     E[node]=(Edge){v,w,head[u]};
24     head[u]=node;
25 }
26 
27 void spfa_dfs(int s)
28 {
29     vis[s]=1;
30     for(int i=head[s];i!=0;i=E[i].next)
31     {
32         int to=E[i].to,w=E[i].w;
33         if(Dist[s]+w<Dist[to])
34         {
35             if(vis[to]){flag=1;return;}
36             else
37             {
38                 Dist[to]=Dist[s]+w;
39                 spfa_dfs(to);
40             }
41         }
42     }
43     vis[s]=0;
44 }
45 
46 bool check()
47 {
48     flag=0;
49     memset(Dist,0x7f,sizeof(Dist));
50     memset(vis,0,sizeof(vis));
51     for(int i=1;i<=n;i++)
52     {
53         Dist[i]=0;
54         spfa_dfs(i);
55         if(flag) return 1;
56     }
57     return 0;
58 }
59 
60 int main()
61 {
62     scanf("%d",&f);
63     for(int Loop=1;Loop<=f;Loop++)
64     {
65         scanf("%d %d %d",&n,&m,&w);
66         node=0;
67         memset(head,0,sizeof(head));
68         for(int i=1;i<=m;i++)
69         {
70             int s,e,t;
71             scanf("%d %d %d",&s,&e,&t);
72             insert(s,e,t);insert(e,s,t);
73         }
74         for(int i=1;i<=w;i++)
75         {
76             int s,e,t;
77             scanf("%d %d %d",&s,&e,&t);
78             insert(s,e,-t);
79         }
80         if(check()) printf("YES
");
81         else printf("NO
");
82     }
83     return 0;
84 }

NOIP模拟赛 虫洞

NOIP模拟赛虫洞