20140710 loop-I SPFA 二分答案

考试的时候写的dfs找环然后求平均值

当时感觉复杂度不是太高

结果Wa和T了一些后只有40分。。。

正解是二分答案再将所有边减去答案后用SPFA找有无负环即可

 1 #include <cstdio>
 2 #include <queue>
 3 #include <vector>
 4 using namespace std;
 5 #define N 660
 6 #define INF 0x3f3f3f+0.0
 7 
 8 struct edge {
 9     int u,v;
10 };
11 struct edge1 {
12     int u;
13     double len;
14 };
15 
16 int n,m;
17 int map[N][N];
18 vector <edge1> G[N];
19 bool vis[N];
20 double dis[N];
21 int outqueue[N];
22 edge e[1010];
23 
24 bool spfa(double k) {
25     for (int i=1;i<=n;i++) {
26         dis[i]=INF;
27         vis[i]=false;
28         outqueue[i]=0;
29     }
30     vis[1]=true;
31     dis[1]=0;
32     queue <int> q;
33     q.push(1);
34     while (!q.empty()) {
35         int v=q.front();
36         q.pop(); vis[v]=false;
37         outqueue[v]++;
38         if (outqueue[v]>n) return false;
39         for (int i=0;i<G[v].size();i++) {
40             edge1 e=G[v][i];
41             if (dis[v]+e.len-k<dis[e.u]) {
42                 dis[e.u]=dis[v]+e.len-k;
43                 if (!vis[e.u]) {
44                     vis[e.u]=true;
45                     q.push(e.u);
46                 }
47             }
48         }
49     }
50     return true;
51 }
52 
53 double min(double a,double b) {
54     return a<b?a:b;
55 }
56 
57 int main() {
58     scanf("%d%d",&n,&m);
59     for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) map[i][j]=INF;
60     for (int i=1;i<=m;i++) {
61         int u,v;
62         double cost;
63         scanf("%d%d%lf",&u,&v,&cost);
64         map[u][v]=min(map[u][v],cost);
65         e[i].u=u; e[i].v=v;
66     }
67     for (int i=1;i<=m;i++) {
68         edge1 e1;
69         e1.u=e[i].v; e1.len=map[e[i].u][e[i].v];
70         G[e[i].u].push_back(e1);
71     }
72     
73     double l=0.0,r=INF;
74     for (int k=0;k<100;k++) {
75         double mid=(l+r)/2;
76         if (spfa(mid)) l=mid;
77         else r=mid;
78     }
79     printf("%.2lf",l);
80 }

View Code