衆所周知，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:\n", ++kase);
for(int i = 0; i < q; i++)
{
scanf("%d", &p);
if(circle[p] || d[p] == INF || d[p] < 3)
printf("?\n");
else
printf("%d\n", 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("\n");
}
return 0;
}
1221 - Travel Company
旅遊公司規劃旅遊路線，要求走完一條路線後
總收入/總支出 > p
，轉化一下就是
\[ in[0] + in[1] + \cdots + in[k] > p\times(out[0]+out[2]+\cdots+out[k]) \]
\[ in[0] + in[1] + \cdots + in[k] > p\times out[0]+ p \times out[2]+ \cdots+ p \times out[k] \]
\[ (p\times out[0] - in[0])+ (p\times out[1] - in[1]) + \cdots + (p\times 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\n");
else
printf("NO\n");
}
return 0;
}
轉載于:https://www.cnblogs.com/Alruddy/p/7398461.html