最短路径
啥也不会。
所以今天早上没有打比赛然后去改题了，因为T1乘法逆元忘了咋写，T2想了半天想不出来最后发现又要用什么什么不认识的算法，T3那个鬼畜方法谁能想出来啊。
T1
这道题需要用到最短路的部分特别简单，毕竟很显然的是只需要求出每个关键点到每个点的最短路即可，一个点开始燃烧的时间即所有关键点到它的最短路的最小值。
如果时间不会被推迟，那么对于每个点都有一条最短路小于图完全燃烧的时间。
以上都很显然。
接下来根据ybtoj的题解需要用到一些我看不懂的数学方法，根据baidu的结果需要用到dp，我都不会。
T2
斯坦纳树题。
根据OIwiki的搜索结果，是一种很神奇的树。由于它在洛谷的模板题有紫，我感觉我是打不出这题了。
（安详地瘫倒
T3
正反建图，分别求出原点和汇点为1的单源最短路和单汇最短路（这个谁都会）。分别记录单源最短路与单汇最短路中每个点u的最短路中距离1最近的节点为p[u]和rp[u]。
枚举图中每条边，分情况更新答案。
写这个blog的时候改这题改了一半，后面还有点小问题没搞懂，我明天早上早点来机房吧。
upd 2023/7/17 7: 39:
改出来了。
枚举图中每条边，分情况更新答案：
当u=1时，显然没必要更新，因为这种情况会被其他情况覆盖
当v=1时，如果p[u]=u，这种情况不合法（1-u-1），要经过其他边，而经过其他边的情况也会被其他情况覆盖；若p[u]!=u，则用d[u]+w更新答案（很显然，不解释）
当u!=1且v!=1时，如果p[u]=rp[v]，会出现重复经过的点，不合法；如果p[u]!=rp[v]，就用d[u]+rd[v]+w更新答案（也很显然）。
code：
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=4e5+10;
int n,m,h[2][N],nxt[2][M],to[2][M],w[2][M],cnt[2]={-1,-1};
int dis[2][N],p[2][N];
bool vis[N];
struct node{
int dis,id;
bool operator < (const node cmx)const{
return dis>cmx.dis;
}
};
void add(int x,int y,int v,int i){
nxt[i][++cnt[i]]=h[i][x];
h[i][x]=cnt[i];
to[i][cnt[i]]=y;
w[i][cnt[i]]=v;
return;
}
void dijkstra(int i){
memset(vis,false,sizeof vis);
priority_queue<node> q;
dis[i][1]=0;
q.push((node){0,1});
while (!q.empty()){
int u=q.top().id;
q.pop();
if (vis[u]){
continue;
}
vis[u]=true;
for (int j=h[i][u];~j;j=nxt[i][j]){
int v=to[i][j];
if (dis[i][v]>dis[i][u]+w[i][j]){
dis[i][v]=dis[i][u]+w[i][j];
q.push((node){dis[i][v],v});
if (u==1){
p[i][v]=v;
}
else{
p[i][v]=p[i][u];
}
}
}
}
return;
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
memset(dis,0x3f3f3f3f,sizeof dis);
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int s,t,w1,w2;
scanf("%d%d%d%d",&s,&t,&w1,&w2);
add(s,t,w1,0);
add(t,s,w2,0);
add(s,t,w2,1);
add(t,s,w1,1);
}
dijkstra(0);
dijkstra(1);
int ans=0x3f3f3f3f;
for (int u=2;u<=n;u++){
for (int i=h[0][u];~i;i=nxt[0][i]){
int v=to[0][i];
if (v==1){
if (p[0][u]!=u){
ans=min(ans,dis[0][u]+w[0][i]);
}
}
else{
if (p[0][u]!=p[1][v]){
ans=min(ans,dis[0][u]+dis[1][v]+w[0][i]);
}
}
}
}
printf("%d",ans);
return 0;
}
强连通分量
T1
考试的时候基本想出正解，却忘了最长链三个字了。于是没打出来。看完题解之后迅速搞了一下。
易证明ans即为缩点后最长链长度（缩点后每个点点权是其强连通分量中的点数）。
code：
#include
using namespace std;
const int N=1e6+10;
int n,m,h[N],to[N],nxt[N],cnt=-1;
int dfn[N],low[N],col[N],k,Time;
int hh[N],too[N],nxtt[N],cntt=-1,q[N];
stack st;
int dis[N],inn[N];
queue que;
void add(int x,int y){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
return;
}
void addd(int x,int y){
nxtt[++cntt]=hh[x];
hh[x]=cntt;
too[cntt]=y;
return;
}
void dfs(int u){
dfn[u]=low[u]=++Time;
st.push(u);
for (int i=h[u];~i;i=nxt[i]){
int v=to[i];
if (!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if (!col[v]){
low[u]=min(low[u],low[v]);
}
}
if (low[u]==dfn[u]){
col[u]=++k;
while (st.top()!=u){
col[st.top()]=col[u];
st.pop();
}
st.pop();
}
return;
}
int main()
{
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
memset(h,-1,sizeof h);
memset(hh,-1,sizeof hh);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for (int i=1;i<=n;i++){
if (!dfn[i]){
dfs(i);
}
}
for (int i=1;i<=n;i++){
for (int j=h[i];~j;j=nxt[j]){
int v=to[j];
if (col[i]==col[v]){
continue;
}
addd(col[i],col[v]);
inn[col[v]]++;
}
}
for (int i=1;i<=n;i++){
q[col[i]]++;
}
for (int i=1;i<=k;i++){
if (!inn[i]){
que.push(i);
dis[i]=q[i];
}
}
while (!que.empty()){
int u=que.front();
que.pop();
for (int i=hh[u];~i;i=nxtt[i]){
int v=too[i];
inn[v]--;
dis[v]=max(dis[v],dis[u]+q[v]);
if (!inn[v]){
que.push(v);
}
}
}
int ans=0;
for (int i=1;i<=k;i++){
ans=max(ans,dis[i]);
}
printf("%d",ans);
return 0;
}
T2
几乎是板题，不解释。但是考试的时候也是忘了最长链三个字，于是考场上写了一个近似于SPFA的bfs。
回头看完题解之后一看自己的代码，这不就是一个SPFA吗。于是稍加修改就过了。
code:
#include
using namespace std;
const int N=5e5+10;
int n,m,h[N],to[N],nxt[N],cnt=-1,q[N],p,s;
int dfn[N],low[N],col[N],k,Time;
stack st;
bool j[N],vis[N];
int hh[N],too[N],nxtt[N],cntt=-1,qq[N],jj[N];
int ans[N];
queue que;
void add(int x,int y){
nxt[++cnt]=h[x];
h[x]=cnt;
to[cnt]=y;
return;
}
void addd(int x,int y){
nxtt[++cntt]=hh[x];
hh[x]=cntt;
too[cntt]=y;
return;
}
void dfs(int u){
dfn[u]=low[u]=++Time;
st.push(u);
for (int i=h[u];~i;i=nxt[i]){
int v=to[i];
if (!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if (!col[v]){
low[u]=min(low[u],low[v]);
}
}
if (low[u]==dfn[u]){
col[u]=++k;
while (st.top()!=u){
col[st.top()]=col[u];
st.pop();
}
st.pop();
}
return;
}
int main()
{
freopen("plan.in","r",stdin);
freopen("plan.out","w",stdout);
memset(h,-1,sizeof h);
memset(hh,-1,sizeof hh);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for (int i=1;i<=n;i++){
scanf("%d",&q[i]);
}
scanf("%d%d",&s,&p);
for (int i=1;i<=p;i++){
int x;
scanf("%d",&x);
j[x]=true;
}
for (int i=1;i<=n;i++){
if (!dfn[i]){
dfs(i);
}
}
s=col[s];
for (int i=1;i<=n;i++){
for (int j=h[i];~j;j=nxt[j]){
int v=to[j];
if (col[i]==col[v]){
continue;
}
addd(col[i],col[v]);
}
}
for (int i=1;i<=n;i++){
qq[col[i]]+=q[i];
if (j[i]){
jj[col[i]]=true;
}
}
que.push(s);
ans[s]=qq[s];
while (!que.empty()){
int u=que.front();
que.pop();
for (int i=hh[u];~i;i=nxtt[i]){
int v=too[i];
if (ans[v]<ans[u]+qq[v]){
ans[v]=ans[u]+qq[v];
if (!vis[v]){
que.push(v);
vis[v]=true;
}
}
}
vis[u]=false;
}
int cmx=0;
for (int i=1;i<=k;i++){
if (jj[i]){
cmx=max(cmx,ans[i]);
}
}
printf("%d",cmx);
return 0;
}
T3
不会打2-SAT，我待会再看看QAQ。