最短路（dijkstra）
无法处理负边权，时间复杂度O(mlogn)
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
//#define A puts("Yes")
//#define B puts("No")
#define fi first
#define se second
#define pi pair<ll,ll>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
typedef unsigned int uint;
const int N=1e6+5;
const ll mo=1e9+7;
const int inf=1e9;
//set<int,greater<int>> s;
priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> q;
int tot=1,nex[N*2],head[N],to[N],n,m,s,x,y,z;
ll w[N*2],d[N];
bool vis[N];
void add(int x,int y,int z){
to[++tot]=y; nex[tot]=head[x]; head[x]=tot; w[tot]=z;
}
void dij(int s){
fo(i,1,n) d[i]=inf;
d[s]=0;
q.push(mk(0,s));
while (!q.empty()) {
x=q.top().se;
q.pop();
if (vis[x]) continue;
vis[x]=1;
for (int i=head[x];i;i=nex[i]) {
int v=to[i];
if (d[v]>d[x]+w[i]) {
d[v]=d[x]+w[i];
q.push(mk(d[v],v));
}
}
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
fo(i,1,m) {
cin>>x>>y>>z;
add(x,y,z);
}
dij(s);
fo(i,1,n) cout<<d[i]<<" ";
return 0;
}
abc375_g
判断某条边是不是1到n最短路上的必经边
dis1[x],f[x]分别表示1-x的最短路长度以及在最短路长度限制下到达x的不同路径数量，
dis2，g表示从n出发的
若(x,y)为必经边，则\(dis1[x]+w(x,y)+dis2[y]=dis1[n]\)且\(f[x]*g[y]=f[n]\)
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll inf = 1ll << 60;
const int N = 2e5 + 10;
const int mo = 998244353;
const ll mo1 = 1e9 + 7;
const ll mo2 = 1e9 + 9;
ll n, m, x, y, z, w[N * 2], dis1[N], dis2[N];
int tot = 1, to[N * 2], nex[N * 2], head[N], d[N];
pi f[N], g[N];
bool vis[N];
priority_queue<pi, vector<pi>, greater<pi>> q;
void add(int x, int y, ll z) {
to[++tot] = y; nex[tot] = head[x]; head[x] = tot; w[tot] = z;
}
void dij(int s, pi f[], ll dis[]) {
fo(i, 1, n) dis[i] = inf, vis[i] = 0;
dis[s] = 0;
q.push(mk(0, s));
while (!q.empty()) {
x = q.top().se; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x];i;i = nex[i]) {
int v = to[i];
if (dis[v] > dis[x] + w[i]) {
dis[v] = dis[x] + w[i];
q.push(mk(dis[v], v));
}
}
}
fo(i, 1, n) d[i] = 0;
fo(i, 2, tot) {
x = to[i]; y = to[i ^ 1]; z = w[i];
if (dis[x] + w[i] == dis[y]) {
d[y]++;
}
}
queue<int> q;
while (!q.empty()) q.pop();
fo(i, 1, n) if (!d[i]) q.push(i), f[i] = mk(1, 1);
while (!q.empty()) {
x = q.front(); q.pop();
for (int i = head[x];i;i = nex[i]) {
int v = to[i];
if (dis[v] == dis[x] + w[i]) {
d[v]--;
f[v] = mk((f[v].fi + f[x].fi) % mo1, (f[v].se + f[x].se) % mo2);
if (!d[v]) q.push(v);
}
}
}
}
bool ans[N * 2];
void solve()
{
cin >> n >> m;
fo(i, 1, m) {
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
dij(1, f, dis1);
dij(n, g, dis2);
fo(i, 2, tot) {
x = to[i]; y = to[i ^ 1]; z = w[i];
if (f[x].fi * g[y].fi % mo1 == f[n].fi && f[x].se * g[y].se % mo2 == f[n].se && dis1[x]+w[i]+dis2[y]==dis1[n]) {
// cout << x << " " << y << "\n";
ans[i / 2] = 1;
}
}
fo(i, 1, m) cout << (ans[i] ? "Yes" : "No") << "\n";
}
int main()
{
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
Floyed
abc375f
两种操作
1.路径i不再可以通行
2.询问dis(x,y)
显然将询问离线，然后倒着加边，每次加入一条边后，考虑更新。
此时f[x][y]表示的是只通过当前加入的边的情况下，x到y的最短路，那么我们枚举通过新加这条边的路径的两个端点即可。
#include<bits/stdc++.h>
#define ll long long
#define fo(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
#define eb emplace_back
#define mk make_pair
using namespace std;
const int N = 505;
const int M = 2e5 + 5;
const ll inf = 1ll << 60;
ll f[N][N], n, m, q, ans[M], tot;
bool bz[M];
struct node {
ll x, y, z;
};
node e[M];
struct key {
ll op, x, y;
};
key c[M];
void cmin(ll& x, ll y) {
x = min(x, y);
}
void solve() {
cin >> n >> m >> q;
fo(i, 1, m) cin >> e[i].x >> e[i].y >> e[i].z;
fo(i, 1, q) {
cin >> c[i].op >> c[i].x;
if (c[i].op == 2) {
cin >> c[i].y;
}
else bz[c[i].x] = 1;
}
fo(i, 1, n) fo(j, 1, n) f[i][j] = inf;
fo(i, 1, n) f[i][i] = 0;
fo(i, 1, m) if (!bz[i]) {
cmin(f[e[i].x][e[i].y], e[i].z);
cmin(f[e[i].y][e[i].x], e[i].z);
}
fo(k, 1, n) fo(i, 1, n) fo(j, 1, n) cmin(f[i][j], f[i][k] + f[k][j]);
ll id, x, y, z;
fd(i, q, 1) {
id = c[i].x;
x = e[id].x; y = e[id].y; z = e[id].z;
if (c[i].op == 1) {
fo(a, 1, n) fo(b, 1, n) {
cmin(f[a][b], f[a][x] + z + f[y][b]);
cmin(f[a][b], f[a][y] + z + f[x][b]);
}
}
else {
x = c[i].x; y = c[i].y;
if (f[x][y] == inf) ans[++tot] = -1;
else ans[++tot] = f[x][y];
}
}
fd(i, tot, 1) cout << ans[i] << "\n";
}
int main() {
// freopen("data.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin>>T;
while (T--) {
solve();
}
return 0;
}
传递闭包
跟floyed一样，可以采用bitset优化
#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
using namespace std;
const int N=1005;
typedef long long ll;
bitset<N> b[N];
int n,x;
int main(){
// freopen("data.in","r",stdin);
scanf("%d",&n);
fo(i,1,n) {
b[i].reset();
fo(j,1,n) {
scanf("%d",&x);
if (x) {
b[i][j]=1;
}
}
}
fo(k,1,n) {
fo(i,1,n) if (b[i][k]) b[i]|=b[k];
}
fo(i,1,n) {
fo(j,1,n) {
printf("%d ",b[i][j]==1?1:0);
}
printf("\n");
}
return 0;
}
差分约束
[ABC216G] 01Sequence
你需要构造出一个长度为 \(n\) 的 \(01\) 序列，满足 \(m\) 个限制 \((l_i,r_i,x_i)\)：在 \([l_i,r_i]\) 这段区间内，序列上 \(1\) 的个数不小于 \(x_i\)。你需要保证你的方案中包含 \(1\) 的个数最小。
数据保证有解。
\(1 \le n,m \le 2 \times 10^5\)
设\(z_i\)表示1到i中0的数量，那么限制有
- \(z_i \le z_{i-1}+1\)
- \(z_{i-1} \le z_{i}\)
- \(z_{r_i}-z_{l_i-1}\le r_i-l_i+1-x_i\)
- \(z_0=0\)
将第三个变形，得到\(z_{r_i}\le r_i-l_i+1-x_i+z_{l_i-1}\)
那么我们得到的就是最短路的形式，因为我们求的是\(z_n\)的最大值，最大能够取得就是不等式右边的最小值，所以等价于最短路，因为所有边权都是正的，直接用dij即可。
#include<bits/stdc++.h>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define pi pair<ll,ll>
#define eb emplace_back
//#define A puts("YES")
//#define B puts("NO")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
//const ll mo1=1e9+7;
//const ll mo2=1e9+9;
const ll mo = 19260817;
const ll P = 131;
const ll Q = 13331;
const ll inf = 1ll << 60;
const int N = 2e5 + 5;
const int M = 1e6 + 5;
int tot = 1, to[M * 2], nex[M * 2], head[N], w[M * 2], d[N];
int n, m;
bool vis[N];
void add(int x, int y, int z) {
to[++tot] = y; nex[tot] = head[x]; head[x] = tot; w[tot] = z;
}
void dij(int s) {
priority_queue<pi, vector<pi>, greater<pi>> q;
fo(i, 1, n) d[i] = n;
q.push(mk(0, s));
while (!q.empty()) {
int x = q.top().se; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x];i;i = nex[i]) {
int v = to[i];
if (d[v] > d[x] + w[i]) {
d[v] = d[x] + w[i];
q.push(mk(d[v], v));
}
}
}
}
int main() {
// freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
fo(i, 1, n) {
add(i - 1, i, 1);
add(i, i - 1, 0);
}
int l, r, x;
fo(i, 1, m) {
cin >> l >> r >> x;
add(l - 1, r, r - l + 1 - x);
}
dij(0);
// fo(i,1,n) cout<<d[i]<<" ";
//
// return 0;
fo(i, 1, n) cout << -d[i] + 1 + d[i - 1] << " ";
}