众所周知，bellman_ford算法最常用的性质是判负环
也可以求最短路，SPFA算法改自Bellman_Ford。
1074 - Extended Traffic
((u,v))的边权是$ (b[v] - b[u])^3$，输出从顶点1到各点最短路径，因为存在负环，所以从负环到达的点的最短路是-inf。
- 如果最短路径小于3（包括负数）输出 '？'
- 否则输出最短路
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 200 + 5;
int t, kase = 0;
int a[N];
struct Edge
{
int u,v,w;
Edge(){}
Edge(int a, int b, int c): u(a),v(b),w(c) {}
};
vector<Edge> edges;
vector<int> G[N];
int n,m,q,p;
void init(int n)
{
edges.clear();
for(int i = 0; i <= n; i++) G[i].clear();
}
void addedge(int u, int v, int w)
{
edges.push_back(Edge(u,v,w));
int m = edges.size();
G[u].push_back(m-1);
}
int d[N], inque[N], cnt[N], circle[N];
void dfs(int u)
{
circle[u] = 1;
for(int i = 0; i < G[u].size(); i++)
{
Edge &e = edges[G[u][i]];
int v = e.v;
if(circle[v]) continue;
dfs(v);
}
}
bool Bellman_ford(int s)
{
memset(d, 0x3f, sizeof(d));
memset(cnt, 0, sizeof(cnt));
memset(inque, 0, sizeof(inque));
memset(circle, 0, sizeof(circle));
d[s] = 0; inque[s] = 1;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop(); inque[u] = 0;
for(int i = 0; i < G[u].size(); i++)
{
Edge &e = edges[G[u][i]];
int v = e.v;
if(circle[v]) continue;
if(d[v] > d[u] + e.w)
{
d[v] = d[u] + e.w;
if(!inque[v])
{
cnt[v]++;
Q.push(v);
inque[v] = 1;
if(cnt[v] > n) dfs(v);
}
}
}
}
return true;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
init(n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d%d", &u, &v);
w = (a[v]- a[u]);
w = w*w*w;
addedge(u,v,w);
}
Bellman_ford(1);
scanf("%d", &q);
printf("Case %d:
", ++kase);
for(int i = 0; i < q; i++)
{
scanf("%d", &p);
if(circle[p] || d[p] == INF || d[p] < 3)
printf("?
");
else
printf("%d
", d[p]);
}
}
return 0;
}
1108 - Instant View of Big Bang
穿越回去看大爆炸，找到可以通往负环的点作为起点，并将起点列出来。
思路
可以将图反过来建，就转变成了可以从负环走到的点，跟上题一样。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 1000 + 5;
int t, kase = 0;
struct Edge
{
int u,v,w;
Edge(){}
Edge(int a, int b, int c): u(a),v(b),w(c) {}
};
vector<Edge> edges;
vector<int> G[N];
int n,m;
void init(int n)
{
edges.clear();
for(int i = 0; i <= n; i++) G[i].clear();
}
void addedge(int u, int v, int w)
{
edges.push_back(Edge(u,v,w));
int m = edges.size();
G[u].push_back(m-1);
}
int d[N], inque[N], cnt[N], circle[N];
void dfs(int u)
{
circle[u] = 1;
for(int i = 0; i < G[u].size(); i++)
{
Edge &e = edges[G[u][i]];
int v = e.v;
if(circle[v]) continue;
dfs(v);
}
}
bool Bellman_ford(int s)
{
queue<int> Q;
for(int i = 0; i < n; i++)
{
d[i] = cnt[i] = 0;
inque[i] = 1;
circle[i] = 0;
Q.push(i);
}
while(!Q.empty())
{
int u = Q.front(); Q.pop(); inque[u] = 0;
for(int i = 0; i < G[u].size(); i++)
{
Edge &e = edges[G[u][i]];
int v = e.v;
if(circle[v]) continue;
if(d[v] > d[u] + e.w)
{
d[v] = d[u] + e.w;
if(!inque[v])
{
cnt[v]++;
Q.push(v);
inque[v] = 1;
if(cnt[v] > n) dfs(v);
}
}
}
}
return true;
}
int u,v,w;
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
init(n);
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &w);
addedge(v, u, w);
}
Bellman_ford(0);
printf("Case %d:", ++kase);
int f = 0;
for(int i = 0; i < n; i++)
if(circle[i])
{
printf(" %d", i);
f = 1;
}
if(f == 0)
printf(" impossible");
printf("
");
}
return 0;
}
1221 - Travel Company
旅游公司规划旅游路线，要求走完一条路线后 总收入/总支出 > p，转化一下就是
[in[0] + in[1] + cdots + in[k] > p imes(out[0]+out[2]+cdots+out[k])
]
[in[0] + in[1] + cdots + in[k] > p imes out[0]+ p imes out[2]+ cdots+ p imes out[k]
]
[(p imes out[0] - in[0])+ (p imes out[1] - in[1]) + cdots + (p imes out[k] - in[k]) < 0
]
就直接令(w = out*p - in) 最后结出现一个负环即可
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 1000 + 5;
int t, kase = 0;
int n,m,p;
struct Edge
{
int u,v,w;
Edge(){}
Edge(int a, int b, int c): u(a), v(b), w(c) {}
};
vector<Edge> edges;
vector<int> G[N];
void init(int n)
{
edges.clear();
for(int i = 0; i <= n; i++) G[i].clear();
}
void addedge(int u, int v, int w)
{
edges.push_back(Edge(u, v, w));
int m = edges.size();
G[u].push_back(m-1);
}
int cnt[N], inque[N], d[N];
bool Bellman_ford()
{
queue<int> Q;
for(int i = 0; i < n; i++)
{
inque[i]= 1;
d[i] = 0;
cnt[i] = 0;
Q.push(i);
}
while(!Q.empty())
{
int u = Q.front(); Q.pop(); inque[u] = 0;
for(int i = 0; i < G[u].size(); i++)
{
Edge &e = edges[G[u][i]];
int v = e.v;
if(d[v] > d[u] + e.w)
{
d[v] = d[u] + e.w;
if(!inque[v])
{
inque[v] = 1;
cnt[v]++;
Q.push(v);
if(cnt[v] > n)
return false;
}
}
}
}
return true;
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d%d%d", &n, &m, &p);
init(n);
for(int i = 0; i < m; i++)
{
int u,v,in,out,w;
scanf("%d%d%d%d", &u, &v, &in, &out);
w = p*out - in;
addedge(u, v, w);
}
printf("Case %d: ", ++kase);
if(!Bellman_ford())
printf("YES
");
else
printf("NO
");
}
return 0;
}