目录
负权环
意即边权和为负数的环， 被较多地称为负环。
Dijkstra 算法不能用在有负权环的图上， 否则会无法保证得出正确的结果。
负环可以用 Bellman-Ford 系算法判。
怎么判
无负权环的图里， 最短路的节点数一定 (le) 图中的节点总数。
Bellman-Ford判： n-1 轮迭代之内， 算法结束， 则无负环。
队列优化 Bellman-Ford判：
1.记录最短路上的节点个数
2.记录节点入队次数，达到 n 则有负环
通常情况下第一种算法效率较高， 可以一起使用。
Sightseeing Cows
0/1 分数规划 + 负环， 写一题同时熟悉两个不熟的算法，挺有意思。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1006;
const int M = 5006;
const double eps = 1e-6;
int n,m,f[N];
int ct, hd[N], nt[M<<1], vr[M<<1]; double w[M<<1];
void ad(int x,int y,double z) {
vr[++ct]=y; w[ct]=z, nt[ct]=hd[x], hd[x]=ct;
}
double dist[N];
bool inq[N];
int cnt[N];
bool SPFA() {
queue<int>q;
for(int i=1;i<=n;++i) {
q.push(i);
inq[i] = 1;
dist[i] = 0;
}
memset(cnt,0,sizeof cnt);
while(q.size()) {
int x=q.front(); q.pop(); inq[x]=0;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(dist[y]>dist[x]+w[i]) {
dist[y] = dist[x]+w[i];
if(++cnt[y]>n) return 1;
// if(cnt[y]>=n) return true;
if(!inq[y]) {inq[y]=1, q.push(y);}
}
}
}
return 0;
}
int x[M], y[M], z[M];
bool check(double mid) {
ct=0; memset(hd,0,sizeof hd);
for(int i=1;i<=m;++i) {
ad(x[i],y[i],mid*z[i]-f[x[i]]);
}
return SPFA();
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i) {
scanf("%d", &f[i]);
}
for(int i=1;i<=m;++i) {
scanf("%d %d %d",&x[i],&y[i],&z[i]);
}
double l=0, r=1000;
while(r-l>eps)
{
double mid = (l+r) / 2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.2f", l);
return 0;
}
差分约束系统
直接抄书
差分约束系统 是一种 N 元 1 次不等式组， 包含 N 个变量 (X_1cdots X_n) 以及 M 个约束条件， 每个约束条件都是由两个变量作差构成的， 形如 (X_i-X_jle w_k) 。求解的目标是求出一组可行解 (X_1cdots X_n) 使得这 M 个约束条件都满足。
依着这个 naive 的变形 (X_i-X_jle w_k Rightarrow X_ile X_j+w_k) ， 将系统中所有变量看作一个有向图中的节点， 对于每个约束， 从节点 j 向节点 i 连一条长度为 (w_i) 的有向边。
对于一个系统，若有一组可行解 ({a_1cdots a_n}) ， 那么 ({a_1+Deltacdots a_n+Delta}) 也是一组解。
求一组非正数解的方法：假设 (X_i le 0) ，新建一个 0 号节点， 令 (X_0 = 0) 。 这样一来， 就多了 N 个形如 (X_i-X_0le0) 的约束， 再继续连边。
设 dist[0] = 0， 从节点 0 求 SSSP， 若图中存在负环， 则无解， 反之 (X_i = dist[i]) 。
对于此种形式的约束条件：(X_i-X_j ge w_i) ， 可以将它转化成最短路; 也可以改为计算单源最长路， 存在正环则无解。
Intervals
把值域做个前缀和， 约束就转为 (S[b_i]-S[a_i-1] ge c_i) 。
求出的解还需要满足以下几个条件：
- (s[k]-s[k-1]ge0)， 即要合理。
- (s[k]-s[k-1]le1)， 即每个数只能选一次。
最后由 -1 为起点求单源最长路。(dist[-1]=0)
#include<bits/stdc++.h>
using namespace std;
const int N = 50013;
int n, maxlen;
int ct, hd[N], nt[N<<3], vr[N<<3], w[N<<3];
void ad(int x,int y,int z) {
vr[++ct]=y, w[ct]=z, nt[ct]=hd[x], hd[x]=ct;
}
queue<int>q;
int dist[N];
bool inq[N];
int SPFA(int s) {
for(int i=0;i<=maxlen;++i) dist[i] = -2147483600;
dist[s] = 0;
q.push(s);
inq[s] = true;
while(q.size()) {
int x=q.front(); q.pop(); inq[x]=false;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(dist[y]<dist[x]+w[i]) {
dist[y] = dist[x]+w[i];
if(!inq[y]) {inq[y]=true; q.push(y);}
}
}
}
return dist[maxlen];
}
int main() {
cin>>n;
for(int i=1;i<=n;++i) {
int a,b,c; scanf("%d%d%d",&a,&b,&c);
// s[b] - s[a-1] >= c
ad(a-1,b,c);
maxlen = max(maxlen, b);
}
int s = maxlen + 2;
for(int i=0;i<maxlen;++i) {
// -1 + 0 >= s[i+1]
ad(i,i+1,0);
ad(i+1,i,-1);
}
ad(s,0,0); ad(0,s,-1);
cout << SPFA(s);
return 0;
}
割边割点
割边显然一定在搜索树里， 且简单环上显然没有割边。
//割边
//可以处理有重边情况的代码
void tarjan(int x, int in_edge) {
dfn[x] = low[x] ++ dfncnt;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(!dfn[y]) {
tarjan(y,i);
low[x] = min(low[x],low[y]);
if(low[y]>dfn[x])
bridge[i] = bridge[i^1] = true; // 边的编号从 2 开始
} else if(i!=(in_edge^1))
low[x] = min(low[x],dfn[y]);
}
}
//割点
void tarjan(int x) {
dfn[x] = low[x] = ++dfntot;
int flag = 0;
for(int i=hd[x];i;i=nt[i]) {
int y=vr[i];
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
if(low[y]>=dfn[x]) {
++flag;
if(x!=root || flag>1) cut[x] = true;
}
} else low[x] = min(low[x],dfn[y]);
}
}
BLO
主要是数数， 割点倒是其次。不过这道题的数数确实能帮助加深对割边割点算法的理解。
#include<bits/stdc++.h>
using namespace std;
const int N = 100003;
const int M = 500003;
int n,m;
int ct,hd[N],nt[M<<1],vr[M<<1];
void ad(int x,int y) { vr[++ct]=y, nt[ct]=hd[x], hd[x]=ct; }
long long Ans[N];
int dfn[N], low[N], siz[N], dfntot;
bool cut[N];
void tarjan(int x) {
dfn[x] = low[x] = ++dfntot; siz[x] = 1;
int flag=0, sum=0;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(!dfn[y]) {
tarjan(y);
siz[x] += siz[y];
low[x] = min(low[x],low[y]);
if(low[y]>=dfn[x]) {
++flag;
sum += siz[y];
Ans[x] += (long long)siz[y] * (n-siz[y]);
if(x!=1 || flag>1) cut[x] = true;
}
} else low[x] = min(low[x],dfn[y]);
}
if(cut[x])
Ans[x] += (long long)(n-sum-1)*(sum+1) + (n-1);
else
Ans[x] = 2*(n-1);
}
int main()
{
scanf("%d%d", &n,&m);
for(int i=0;i<m;++i) {int x,y;scanf("%d%d",&x,&y);ad(x,y);ad(y,x);}
tarjan(1);
for(int i=1;i<=n;++i) cout << Ans[i] << '
';
return 0;
}
点双和 v-DCC 、 边双和 e-DCC
不存在割点的无向连通图是点双连通图。 v-DCC 是无向图的极大点双联通子图。
一张无向图是点双连通图， 当且仅当其满足以下两个条件之一：
- 节点数不超过 2
- 任意两点都同时包含在至少一个简单环中
不存在割边的无向连通图是边双连通图。 e-DCC 是无向图的极大边双连通子图。
一张无向图是边双连通图， 当且仅当任意一条边都包含在至少一个环中。
点双的求法和缩点
//求法
void tarjan(int x) {
dfn[x] = low[x] = ++dfntot;
stack[++top] = x;
if(x==root && head[x]==0) { // 孤立点
dcc[++dcccnt].push_back(x);
return;
}
int flag = 0;
for(int i=head[x];i;i=next[i]) {
int y = ver[i];
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
if(low[y]>=dfn[x]) {
++flag;
if(x!=root || flag>1) cut[x]=true;
++dcccnt;
int z;
do {
z = stack[top--];
dcc[dcccnt].push_back(z);
} while(z!=y);
dcc[dcccnt].push_back(x);
}
} else low[x]=min(low[x],dfn[y]);
}
}
//缩点
//每个割点向所有包含它的点双联通分量连边
Network
#include<bits/stdc++.h>
using namespace std;
const int N = 100003;
const int M = 200003;
int n,m;
int ct, hd[2][N], nt[M*4], vr[M*4];
void ad(int id,int x,int y) {
vr[++ct]=y, nt[ct]=hd[id][x], hd[id][x]=ct;
}
int dfntot, dfn[N], low[N];
bool bridge[M*2];
void tarjan(int x,int in_edge) {
dfn[x] = low[x] = ++dfntot;
for(int i=hd[0][x];i;i=nt[i]) {
int y = vr[i];
if(!dfn[y]) {
tarjan(y,i);
low[x] = min(low[x],low[y]);
if(low[y]>dfn[x]) bridge[i]=bridge[i^1]= true;
} else if(i!=(in_edge^1))low[x]= min(low[x],dfn[y]);
}
}
int dcc[N], dcctot;
void dfs(int x) {
dcc[x] = dcctot;
for(int i=hd[0][x];i;i=nt[i]) {
int y = vr[i];
if(dcc[y] || bridge[i]) continue;
dfs(y);
}
}
int fa[N], dep[N];
void dfs2(int x) {
for(int i=hd[1][x];i;i=nt[i]) {
int y = vr[i];
if(y==fa[x]) continue;
fa[y] = x;
dep[y] = dep[x]+1;
dfs2(y);
}
}
bool vis[N];
int calc(int x,int y) {
int res = 0;
if(dep[x]>dep[y]) swap(x,y);
while(dep[y]>dep[x]) {
if(!vis[y]) vis[y]=true, ++res;
y = fa[y];
}
while(x!=y) {
if(!vis[x]) vis[x]=true, ++res;
if(!vis[y]) vis[y]=true, ++res;
x = fa[x];
y = fa[y];
}
return res;
}
int main()
{
int id = 0;
while(cin>>n>>m && n && m) {
int Ans = 0;
printf("Case %d:
", ++id);
ct=1; dfntot=0; dcctot=0;
for(int i=1;i<=n;++i) hd[0][i]=hd[1][i]=dfn[i]=dcc[i]=vis[i]=fa[i]=dep[i]=0;
for(int i=1;i<=2*m+1;++i) bridge[i]=0;
for(int i=0;i<m;++i) {int x,y;scanf("%d%d",&x,&y);ad(0,x,y);ad(0,y,x);}
//存图 0 的边
tarjan(1,0);
// 求出割边
for(int i=1;i<=n;++i) if(!dcc[i]) {
++dcctot; dfs(i);
}
// 染色
int pct = ct;
for(int i=2;i<=pct;++i) {
int x=vr[i^1], y=vr[i];
if(dcc[x]==dcc[y]) continue;
ad(1,dcc[x],dcc[y]);
}
// 建出图 1
dfs2(1);
// 求出 fa、dep 数组
Ans = dcctot-1;
int q; cin>>q;
while(q--)
{
int x,y; scanf("%d%d",&x,&y);
Ans -= calc(dcc[x],dcc[y]);
cout << Ans << '
';
}
putchar('
');
}
return 0;
}
Knights of the Round Table
#include<bits/stdc++.h>
using namespace std;
const int N = 1003;
const int M = 1000003;
int n,m, vis[N][N];
int ct, hd[N], nt[M*2+1], vr[M*2+1];
void ad(int x,int y) {
vr[++ct]=y, nt[ct]=hd[x], hd[x]=ct;
}
int dfntot, dfn[N], low[N], dcccnt;
vector<int>dcc[N];
int sta[N], tp;
bool cut[N];
int root;
void tarjan(int x) {
dfn[x] = low[x] = ++dfntot;
if(x==root && hd[x]==0) {
dcc[++dcccnt].clear();
dcc[dcccnt].push_back(x);
return;
}
sta[++tp] = x;
int flag = 0;
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(!dfn[y]) {
tarjan(y);
low[x] = min(low[x],low[y]);
if(low[y]>=dfn[x]) {
++flag;
if(x!=1 || flag>1) cut[x]=true;
dcc[++dcccnt].clear();
int z;
do{
z = sta[tp--];
dcc[dcccnt].push_back(z);
} while(z!=y);
dcc[dcccnt].push_back(x);
}
} else low[x] = min(low[x],dfn[y]);
}
}
bool tag[N];
int col[N];
bool test(int x) {
for(int i=hd[x];i;i=nt[i]) {
int y = vr[i];
if(!tag[y]) continue;
if(!col[y]) {
col[y] = 3-col[x];
if(test(y)) return true;
} else if(col[y]==col[x]) return true;
}
return false;
}
bool good[N];
int main()
{
while(cin>>n>>m && n) {
int Ans = 0;
memset(vis,0,sizeof vis);
for(int i=0;i<m;++i) {
int x,y; scanf("%d%d",&x,&y);
vis[x][y] = vis[y][x] = true;
}
ct = 1; tp = dcccnt = dfntot = 0;
for(int i=1;i<=n;++i) hd[i]=dfn[i]=cut[i]=0;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j) if(!vis[i][j]) {
ad(i,j); ad(j,i);
}
for(int i=1;i<=n;++i) if(!dfn[i]) {
root = i;
tarjan(i);
}
memset(good,0,sizeof good);
for(int i=1;i<=dcccnt;++i) {
for(int j=0;j<(int)dcc[i].size();++j) tag[dcc[i][j]] = 1;
col[dcc[i][0]]=1;
if(test(dcc[i][0])) for(int j=0;j<(int)dcc[i].size();++j) good[dcc[i][j]] = true;
for(int j=0;j<(int)dcc[i].size();++j) col[dcc[i][j]] = tag[dcc[i][j]] = 0;
}
for(int i=1;i<=n;++i) if(good[i]) ++Ans;
cout << n-Ans << '
';
}
return 0;
}