图论升级
A. Codeforces 296D
重题
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=503,INF=1050000000;
int g[maxn][maxn],n,a[maxn];
long long ans[maxn];
long long floyd(int I){
long long sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][a[I]]+g[a[I]][j]);
}
}
for(int i=n;i>=I;i--){
for(int j=n;j>=I;j--){
sum+=g[a[i]][a[j]];
}
}
return sum;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&g[i][j]);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int i=n;i>=1;i--)ans[i]=floyd(i);
for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
return 0;
}B. Codeforces 954D
题意
给你 \(n\) 个点和 \(m\) 条边，还给了一个起点和终点，问最多加多少条边，可以使得起点到终点的最短路不会变小。 \((n,m\le 1000)\)
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。解
求一遍最短路再枚举所有可能的边。
C. Codeforces 821D
题意
\(n*m\) 地图,有 \(k\) 个位置是点亮的,有4个移动方向,每次可以移动到相邻的点亮位置,每次站在初始被点亮某个位置,暂时使某行或该某列全部点亮,花费为1,下一次使用时,上一次暂时点亮被熄灭. \((n,m\le 10^4)\)
解
将行、列看成点，将有关的点连边，求最短路。
D. HDU 3686
题意
一张无向图，很多询问，每次给你两个点，问你从一个点到另一个点必须经过的点有多少个。
解
点双连通分量模板题（之一）。
先缩点，求出每条边所属的点双，然后弄出点双树，答案就是两个节点在点双树上的距离，用lca求得。
Code
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=200003,maxlog=21;
struct edge{int to,next;}e[maxn<<1];
int head[maxn],cnte;
void add(int u,int v){e[++cnte].to=v,e[cnte].next=head[u],head[u]=cnte;}
int n,m,n2,low[maxn],dfn[maxn],cntdfn,iscut[maxn],ble[maxn],cntbcc,vis[maxn],stk[maxn],top,num[maxn],lg[maxn],fa[maxn][maxlog],dep[maxn];
int flip(int i){return i&1?i+1:i-1;}
vector<int> g[maxn];
void ADD(int u,int v){g[u].push_back(v),g[v].push_back(u);}
void tarjan(int u,int tp){
int son=0;
dfn[u]=low[u]=++cntdfn;
for(int i=head[u];i;i=e[i].next){
if(vis[i])continue;
vis[i]=vis[flip(i)]=1;
stk[++top]=i;
int v=e[i].to;
if(!dfn[v]){
son++;
tarjan(v,tp);
low[u]=min(low[u],low[v]);
if(u==tp?son>=2:low[v]>=dfn[u])iscut[u]=1;
if(low[v]>=dfn[u]){
cntbcc++;
int x;
do{
x=stk[top--];
ble[x]=ble[flip(x)]=cntbcc;
}while(x!=i);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void make(){
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i);
n2=cntbcc;
for(int i=1;i<=n;i++)if(iscut[i])num[i]=++n2;
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(iscut[u])ADD(ble[i],num[u]),ADD(num[u],ble[i]);
if(iscut[v])ADD(ble[i],num[v]),ADD(num[v],ble[i]);
}
}
// printf("cntbcc:%d\n",cntbcc);
// printf("n2:%d\n",n2);
// for(int i=1;i<=cnte;i++)printf("%d ",ble[i]);puts("");
for(int i=1;i<=n2;i++){
sort(g[i].begin(),g[i].end());
g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end());
// printf("%d: ",i);for(auto j:g[i])printf("%d ",j);puts("");
}
}
void init(int u,int last){
vis[u]=1;
fa[u][0]=last;
for(int i=1;(1<<i)<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<int(g[u].size());i++){
int v=g[u][i];
if(v==last)continue;
dep[v]=dep[u]+1;
init(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])x=fa[x][lg[dep[x]-dep[y]]];
if(x==y)return x;
for(int i=lg[dep[x]];i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main(){
for(int i=2;i<maxn;i++)lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);
while(scanf("%d%d",&n,&m),n||m){
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
make();
for(int i=1;i<=cnte;i++)vis[i]=0;
for(int i=1;i<=n2;i++)if(!vis[i])init(i,0);
int Q;
scanf("%d",&Q);
while(Q--){
int x,y;
scanf("%d%d",&x,&y);
x=ble[x<<1],y=ble[y<<1];
printf("%d\n",(dep[x]+dep[y]-(dep[lca(x,y)]<<1))>>1);
}
for(int i=1;i<=n;i++){
head[i]=low[i]=dfn[i]=iscut[i]=num[i]=0;
}
for(int i=1;i<=cnte;i++){
ble[i]=0;
}
for(int i=1;i<=n2;i++){
g[i].clear();
vis[i]=dep[i]=0;
for(int j=0;j<maxlog;j++)fa[i][j]=0;
}
cnte=cntdfn=cntbcc=top=0;
}
return 0;
}E. Codeforces 11D
题意
给一张图，求简单环的个数。 \((n\le 19)\)
解
状压dp。
\(dp[S][u]\) 表示走了集合 \(S\) 找到的环数。
如果当前扫到了一个点，而集合里已经包含了这个点，那么说明找到了一个（也可能是多个）环。我们钦定这个环从 \(lowbit(S)\) 开始（为了防止重复计算）。
#include<bits/stdc++.h>
using namespace std;
const int maxn=19;
int g[maxn][maxn],n,m;
long long ans,dp[1<<maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
u--,v--;
g[u][v]=g[v][u]=1;
}
for(int i=0;i<n;i++){
dp[1<<i][i]=1;
}
for(int t=1;t<(1<<n);t++){
for(int u=0;u<n;u++){
if((t>>u)&1){
for(int v=0;v<n;v++){
if((t&-t)<=(1<<v)&&g[u][v]){
if((t&-t)==(1<<v)){
ans+=dp[t][u];
}
if(((t>>v)&1)==0){
dp[t|(1<<v)][v]+=dp[t][u];
}
}
}
}
}
}
printf("%lld\n",(ans-m)>>1);
return 0;
}
更多精彩
