百度有一位非常有名的大科学家，这位大科学家有很多藏书。
大科学家有一个图书馆，所以放书的容量也随之增加了，图书馆可以看成一个长度为$N$的序列，一开始里面放着 $N$ 本书，每本书都记载了一个特定元素的信息，书中的元素各不相同。
大科学家会先进行若干次研究，最后进行一次科学实验，这次实验需要选取一些元素放在一起来进行。每次研究，大科学家会从图书馆中的某些位置抽出一些书来看，然后得出“如果$x$位置上的书对应的元素被拿来做实验了，那么区间$[l,r]$位置上的书对应的元素也必须拿来做实验，否则会爆炸”这样的结论。
大科学家有不止$N$本书（也就是说世界上有不止$N$种元素），但是他自己没时间给图书馆换书，所以他雇了一个实习生，这个实习生会时不时地拿出一本从来没被放入图书馆的书，然后替换掉图书馆中某个位置原来的书（所以对于大科学家得到的两次看似一样的研究结果，可能由于图书馆中的书被换了，它们的实质内容可能不一样）。
每本书还记载着对应元素的非负污染值，大科学家希望在完成一次科学实验的前提下（不能不选任何元素），这次实验的总污染值最小。作为一个旁观者，你能看到科学家做的所有研究结果以及实习生换书的顺序，然后你需要告诉大科学家，这个最小总污染值是多少。
由于大科学家精力有限，所以它只能得出不多的实验结论（具体参见数据范围）。
第一行一个正整数 $N$，代表图书馆的容量。
接下来一行 $N$ 个数，第 $i$ 个非负整数 $a_i$ 代表最开始图书馆中第 $i$ 本书所描述的元素的污染值。
接下来一行一个整数 $M$，代表事件的总数。
接下来 $M$ 行，每行代表一个事件：
若为 $0$ $x$ $y$，代表实习生拿了一本新书替换了 $x$ 位置的书，新书对应元素的污染值为 $y$。
若为 $1$ $x$ $l$ $r$，代表大科学家得到了新的结果，如果 $x$ 位置的书对应的元素加入了实验，那么 $[l,r]$ 区间内的书对应的元素都必须拿来做实验。
保证大科学家的书籍总数$(N+ 新书数量)\le 10^5$。
每个元素的污染值 $0\le (a_i,y)\le 10^9$。
保证 $1\le x\le N$，$1 \le l \le r \le N$，$M \le 10^5$。
由于大科学家的精力有限，做不了太多的实验，所以我们保证 $\sum(r-l+1) \le 10^5$。
输出一个整数，代表最小总污染值。
一开始书架上有 $5$ 本书，我们记这些元素的编号顺次为 $1$,$2$,$3$,$4$,$5$，他们的污染值分别为 $1$,$10$,$100$,$1000$,$10000$。
一共有 $4$ 个事件：
于是在所有可能的方案中，单选一个元素 $2$ 来做实验是总污染值最小的，因为如果选择元素 $1$ 或元素 $6$，都存在一些绑定关系使得总污染值不可能比 $10$ 更小。
5
1 10 100 1000 10000
4
1 1 3 4
1 3 5 5
0 3 0
1 3 1 210[button color="success" url="https://vjudge.net/problem/计蒜客-A1691" outline="default" target="_blank"]👉vjudge_计蒜客-A1691[/button]
看成有向图的话不难发现答案一定在出度为$0$的子图里，只是环比较难以解决，$tarjan$缩点算法可以有效计算强连通分量，即缩圈成点，蓝书上有介绍，强连通分量。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<algorithm>
#define MaxN 100000+100
typedef long long LL;
using namespace std;
const LL inf=1e15+7;
LL value[MaxN];
int book[MaxN];
vector<int>G[MaxN];
stack<int>Sta;
stack<int>copy;
int pre[MaxN];
int low_link[MaxN];
int scc[MaxN];
int dfs_cnt,scc_cnt;
LL result=inf;
void dfs(int now)
{
low_link[now]=pre[now]=++dfs_cnt;
Sta.push(now);
for(int i=0;i<G[now].size();i++)
{
int v=G[now][i];
if(!pre[v])
{
dfs(v);
low_link[now]=min(low_link[now],low_link[v]);
}
else
if(!scc[v])
low_link[now]=min(low_link[now],pre[v]);
}
if(low_link[now]==pre[now])
{
LL sum=0;
bool flag=false;
scc_cnt++;
while(1)
{
int u=Sta.top();
scc[u]=scc_cnt;
sum+=value[u];
for(int k=0;k<G[u].size();k++)
if(scc[G[u][k]]!=0 && scc[G[u][k]]<scc_cnt)
flag=true;
Sta.pop();
if(u==now)
break;
}
if(!flag)
result=min(result,sum);
}
}
void find_scc(int N)
{
dfs_cnt=0;
scc_cnt=0;
memset(pre,0,sizeof(pre));
memset(low_link,0,sizeof(low_link));
memset(scc,0,sizeof(scc));
for(int i=1;i<=N;i++)
if(!pre[i])
dfs(i);
}
int main()
{
int N;
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%lld",&value[i]),book[i]=i;
int M;
scanf("%d",&M);
while(M--)
{
int ope;
scanf("%d",&ope);
if(ope==0)
{
int a;
LL b;
scanf("%d %lld",&a,&b);
book[a]=++N;
value[N]=b;
}
else
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
for(int i=b;i<=c;i++)
G[book[a]].push_back(book[i]);
}
}
find_scc(N);
printf("%lld\n",result);
return 0;
} 本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。
输入第一行给出$2$个正整数$N$ $(2 \le N \le 200，城镇总数)$和$K(城镇间道路条数)$，以及己方大本营和敌方大本营的代号。随后$N-1$行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有$K$行，每行按格式$城镇1$ $城镇2$ 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由$3$个大写英文字母组成的字符串。
按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式$己方大本营\rightarrow 城镇1->...->敌方大本营$输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以$1$个空格分隔，行首尾不得有多余空格。
10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10PAT->PTA->PDS->DBY
3 30 210枚举各种路线的走法，然后把满足条件的路线和最优路线给记录下来。由于要考虑每一条路线，即把每一条路线都给走一遍，所以我们需要回溯
[button color="success" url="https://pintia.cn/problem-sets/994805046380707840/problems/994805049455132672" outline="default" target="_blank"]👉PTA_L3-011_直捣黄龙[/button]
#include<stdio.h>
#include<stdlib.h>
struct cityi //城市数据
{
int arrive_; //可以进入的城市的数目
struct a
{
int cityid; //可以进入的城市
int distance; //去这个城市所需要的距离
}arrive[199+20]; //由于城市上限不超过200个，所以我们就算所有城市都能去也只有199条路。
int enemy;
}citys[199+20]; //同上，不超过200个城市。
int symbol[201]={0}; //标记，如果走过的城市在同一条路线里不会走第二次，因为我们要最快速度最短距离。
int rails=0; //最短距离的路的条数。
int railway[201]; //记录路线
int truerailway[201]; //最终最优路线
int railway_=0; //当前经过的城市的个数
int truerailways=-1; //最优路线经过城市的个数
char cityname[201][4]; //代号转换，将名字转换成数字，后面的conversion函数就是转换功能。
int maxkill=-1; //最优路线歼敌数
int mixdistance=500000; //最短进攻距离
int maxtown=-1; //最优路线解放的城镇的数目
int conversion(char name[4],int N); //城镇代号与数字之间的转化
int compare(char name1[4],char name2[4]); //比较城镇是否相同
void seek(int now ,int distance,int kill,int town);
int main()
{
int N,K;
char wgzf;
int amount;
scanf("%d%d",&N,&K);
scanf("%c",&wgzf);
scanf("%s",cityname[0]);
scanf("%s",cityname[1]);
citys[0].arrive_=0; //初始化第一个城镇（即我方大本营）
citys[0].enemy=0; //我方大本营没有敌军
amount=N-1; //题目要求N-1条路线
int cityname_=2; //已经初始化了两个城镇，所以从第三个城镇开始计数
while(amount--) //输入，并初始化所有城镇注意由于先前只输入一个敌方大本营，并没有输入敌人人数。
{
int number;
scanf("%s",cityname[cityname_]);
scanf("%d",&number);
if(compare(cityname[1],cityname[cityname_])) //判断是否为敌方大本营，是的话初始化敌人个数
{
citys[1].enemy=number;
citys[1].arrive_=0;
}
else
{
citys[cityname_].enemy=number;
citys[cityname_].arrive_=0;
cityname_++;
}
}
while(K--) //输入路线以及距离（注意两个城镇都要初始化）
{
char name1[4];
char name2[4];
int distance;
scanf("%s",name1);
scanf("%s",name2);
scanf("%d",&distance);
int id1,id2;
id1=conversion(name1,N);
id2=conversion(name2,N);
citys[id1].arrive[citys[id1].arrive_].cityid=id2;
citys[id1].arrive[citys[id1].arrive_++].distance=distance;
citys[id2].arrive[citys[id2].arrive_].cityid=id1;
citys[id2].arrive[citys[id2].arrive_++].distance=distance;
}
int times; //标记大本营
symbol[0]=1;
seek(0,0,0,0);
int hh;
printf("%s",cityname[0]);
for(hh=0;hh<truerailways;hh++)
printf("->%s",cityname[truerailway[hh]]);
printf("\n");
printf("%d %d %d",rails,mixdistance,maxkill);
}
int compare(char name1[4],char name2[4]) //比较函数
{
char *p1,*p2;
p1=name1;
p2=name2;
while(*p1==*p2 && *p1!='\0')
{
p1++;
p2++;
}
if(*p1=='\0')
return 1;
else
return 0;
}
int conversion(char name[4],int N) //转换函数，转换城镇代号
{
int i;
for(i=0;i<N;i++)
if(compare(cityname[i],name))
return i;
return -1;
}
void seek(int now ,int distance,int kill,int town) //查询函数，枚举回溯每一条路线
{
kill+=citys[now].enemy;
if(now==1) //终止条件，由于先前定义地方大本营位置为1
{
if(distance<=mixdistance) //是最短距离的时候进行考虑否则直接跳过
{
if(distance<mixdistance)
{
rails=0; //若是新的最短距离，更新最优路线数量
mixdistance=distance;
maxtown=town;
maxkill=kill;
truerailways=railway_;
int times;
for(times=0;times<railway_;times++) //记录最优路线
truerailway[times]=railway[times];
}
else
if(town>=maxtown)
{
if(town>maxtown)
{
maxtown=town;
maxkill=kill;
truerailways=railway_;
int times;
for(times=0;times<railway_;times++) //记录最优路线
truerailway[times]=railway[times];
}
else
if(kill>maxkill)
{
maxkill=kill;
truerailways=railway_;
int times;
for(times=0;times<railway_;times++) //记录最优路线
truerailway[times]=railway[times];
}
}
rails++;
}
return ;
}
int i;
for(i=0;i<citys[now].arrive_;i++) //回溯
{
if(symbol[citys[now].arrive[i].cityid]==0) //判断是否已被标记
{
railway[railway_++]=citys[now].arrive[i].cityid; //记录当前路线
symbol[citys[now].arrive[i].cityid]=1;
seek(citys[now].arrive[i].cityid,distance+citys[now].arrive[i].distance,kill,town+1);
symbol[citys[now].arrive[i].cityid]=0; //
railway_--; //返回初始状态
}
}
}