T1
A. 抵制克苏恩
题目描述
小Q同学现在沉迷炉石传说不能自拔。他发现一张名为克苏恩的牌很不公平。如果你不玩炉石传说，不必担心，小Q同学会告诉你所有相关的细节。炉石传说是这样的一个游戏，每个玩家拥有一个 30 点血量的英雄，并且可以用牌召唤至多 7 个随从帮助玩家攻击对手，其中每个随从也拥有自己的血量和攻击力。小Q同学有很多次游戏失败都是因为对手使用了克苏恩这张牌，所以他想找到一些方法来抵御克苏恩。他去求助职业炉石传说玩家椎名真白，真白告诉他使用奴隶主这张牌就可以啦。如果你不明白我上面在说什么，不必担心，小Q同学会告诉你他想让你做什么。现在小Q同学会给出克苏恩的攻击力是 K ，表示克苏恩会攻击 K 次，每次会从对方场上的英雄和随从中随机选择一个并对其产生 1 点伤害。现在对方有一名克苏恩，你有一些奴隶主作为随从，每名奴隶主的血量是给定的。如果克苏恩攻击了你的一名奴隶主，那么这名奴隶主的血量会减少 1 点，当其血量小于等于 0 时会死亡，如果受到攻击后不死亡，并且你的随从数量没有达到 7 ，这名奴隶主会召唤一个拥有 3 点血量的新奴隶主作为你的随从；如果克苏恩攻击了你的英雄，你的英雄会记录受到 1 点伤害。你应该注意到了，每当克苏恩进行一次攻击，你场上的随从可能发生很大的变化。小Q同学为你假设了克苏恩的攻击力，你场上分别有 1 点、 2 点、 3 点血量的奴隶主数量，你可以计算出你的英雄受到的总伤害的期望值是多少吗？
输入格式
输入包含多局游戏。
第一行包含一个整数 T (T<100) ，表示游戏的局数。
每局游戏仅占一行，包含四个非负整数 K, A, B 和 C ，表示克苏恩的攻击力是 K ，你有 A 个 1 点血量的奴隶主， B 个 2 点血量的奴隶主， C 个 3 点血量的奴隶主。
保证 K 是小于 50 的正数， A+B+C 不超过 7 。
输出格式
对于每局游戏，输出一个数字表示总伤害的期望值，保留两位小数。
样例
样例输入
1
1 1 1 1样例输出
0.25这次连道送分题都没有……其实看题解后感觉第一题还是比较好做的，但考试的时候没想出来。其实如果按dp的思路，先想高维然后优化，但是因为受概率与期望第二题影响，没有去想高维dp，一直在想维护平方的期望啥的，然后没写出来，最后很无奈的交了暴力，然后发现他只有五个测试点……就wa0了……
#include<iostream>
#include<cstdio>
#include<cstring>
#define ma(x) memset(x,0,sizeof(x))
using namespace std;
int T;
int k,a,b,c;
double sh[55],ans;
void dfs(int t,int a,int b,int c,double gl);
int main()
{
// freopen("in.txt","r",stdin);
freopen("cthun.in","r",stdin);
freopen("cthun.out","w",stdout);
cin>>T;
while(T--)
{
ma(sh);ans=0;
scanf("%d%d%d%d",&k,&a,&b,&c);
dfs(1,a,b,c,1);
for(int i=1;i<=k;i++)
ans+=sh[i];
printf("%0.2lf\n",ans);
}
return 0;
}
void dfs(int t,int a,int b,int c,double gl)
{
if(t==k+1)return;
int al=a+b+c;
if(al)sh[t]+=gl/(al+1);
else sh[t]+=1;
dfs(t+1,a,b,c,gl/(al+1));
dfs(t+1,a-1,b,c,a*gl/(al+1));
if(a+b+c<7)
{
dfs(t+1,a+1,b-1,c+1,b*gl/(al+1));
dfs(t+1,a,b+1,c,c*gl/(al+1));
}
else if(a+b+c==7)
{
dfs(t+1,a+1,b-1,c,b*gl/(al+1));
dfs(t+1,a,b+1,c-1,c*gl/(al+1));
}
}
暴力TLE0
#include<iostream>
#include<cstdio>
#include<cstring>
#define ma(x) memset(x,0,sizeof(x))
using namespace std;
int T;
int k,a,b,c;
double sh[55],ans;
void dfs(int t,int a,int b,int c,double gl);
int main()
{
// freopen("in.txt","r",stdin);
freopen("cthun.in","r",stdin);
freopen("cthun.out","w",stdout);
cin>>T;
while(T--)
{
ma(sh);ans=0;
scanf("%d%d%d%d",&k,&a,&b,&c);
dfs(1,a,b,c,1);
for(int i=1;i<=k;i++)
ans+=sh[i];
printf("%0.2lf\n",ans);
}
return 0;
}
void dfs(int t,int a,int b,int c,double gl)
{
if(t==k+1)return;
int al=a+b+c;
if(al)sh[t]+=gl/(al+1);
else sh[t]+=1;
dfs(t+1,a,b,c,gl/(al+1));
dfs(t+1,a-1,b,c,a*gl/(al+1));
if(a+b+c<7)
{
dfs(t+1,a+1,b-1,c+1,b*gl/(al+1));
dfs(t+1,a,b+1,c,c*gl/(al+1));
}
else if(a+b+c==7)
{
dfs(t+1,a+1,b-1,c,b*gl/(al+1));
dfs(t+1,a,b+1,c-1,c*gl/(al+1));
}
【题解】
设f[i][a][b][c][j]为第i回合，剩余a个一血，b个二血，c个三血，受到伤害总共为j概率。初始状态f[0][a][b][c][0]=1;
转移：
1.砍英雄 f[i][a][b][c][j+1]+=f[i-1][a][b][c][j]* 1.0/(a+b+c+1)
2.砍一滴血的奴隶主 f[i][a-1][b][c][j]+=f[i-1][a][b][c]* a/(1+a+b+c)
3.砍两滴血的奴隶主 f[i][a+1][b-1][c+1][j]+=f[i-1][a][b][c]* b/(1+a+b+c) (a+b+c<=6) OR
f[i][a+1][b-1][c][j]+=f[i-1][a][b][c]* b/(1+a+b+c) (a+b+c==7)
4.砍三滴血的奴隶主 f[i][a][b+1][c][j]+=f[i-1][a][b][c]* c/(1+a+b+c) (a+b+c<=6) OR
f[i][a][b+1][c-1][j]+=f[i-1][a][b][c]* c/(1+a+b+c) (a+b+c==7)
最后答案是 ∑f[k][a][b][c][j]*j;
其实理解之后还是比较简单的。
Ps：这个题比较坑的是题中给了个三十，致使好几个人以为伤害到三十后就死了……然后就悲催得爆零了。然后其实这个题可以是四维的。
【标程】
#include<iostream>
#include<cstdio>
#include<cstring>
#define dou double
using namespace std;
int T,k,a,b,c;
double f[55][10][10][10][100];
signed main()
{
// freopen("in.txt","r",stdin);
cin>>T;
while(T--)
{
memset(f,0,sizeof(f));
scanf("%d%d%d%d",&k,&a,&b,&c);
f[0][a][b][c][0]=1;
for(int i=1;i<=k;i++)
for(int ta=0;ta<=7;ta++)
for(int tb=0;tb<=7;tb++)
if(ta+tb>7)break;
else
for(int tc=0;tc<=7;tc++)
if(ta+tb+tc>7)break;
else
for(int j=0;j<=k;j++)
if(f[i-1][ta][tb][tc][j])
{
f[i][ta][tb][tc][j+1]+=f[i-1][ta][tb][tc][j]*(dou)1.0/(dou)(ta+tb+tc+1);
if(ta)f[i][ta-1][tb][tc][j]+=f[i-1][ta][tb][tc][j]*(dou)ta/(dou)(ta+tb+tc+1);
if(ta+tb+tc<=6)
{
if(tb)f[i][ta+1][tb-1][tc+1][j]+=f[i-1][ta][tb][tc][j]*(dou)tb/(dou)(ta+tb+tc+1);
if(tc)f[i][ta][tb+1][tc][j]+=f[i-1][ta][tb][tc][j]*(dou)tc/(dou)(ta+tb+tc+1);
}
else
{
if(tb)f[i][ta+1][tb-1][tc][j]+=f[i-1][ta][tb][tc][j]*(dou)tb/(dou)(ta+tb+tc+1);
if(tc)f[i][ta][tb+1][tc-1][j]+=f[i-1][ta][tb][tc][j]*(dou)tc/(dou)(ta+tb+tc+1);
}
}
double ans=0;
for(int ta=0;ta<=7;ta++)
for(int tb=0;tb<=7;tb++)
for(int tc=0;tc<=7;tc++)
if(ta+tb+tc>7)break;
else
{
for(int j=1;j<=k;j++)
ans+=f[k][ta][tb][tc][j]*(double)j;
}
printf("%0.2lf\n",ans);
}
}
View Code
T2
B. 概率充电器
题目描述
著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?
输入格式
第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的充电元件,通电概率为 p。
第 n+2 行 n 个整数:qiq_iqi。表示 i 号元件直接充电的概率为 qi。
输出格式
输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数
样例
样例输入
3
1 2 50
1 3 50
50 0 0样例输出
1.000000数据范围与提示
对于 100%的数据,n≤500000,0≤p,qi≤100。
真的是个神题，学到了。读完题后很明显是树形概率dp，然而父亲儿子会相互影响，dp有后效性……然后我又想到了高斯消元，首先数据范围太大肯定不是正解，然后也不容易实现，就放弃了，打了个错解过了样例，拿了5分。（其实直接输出n可以拿10分的……）
【题解】
其实可以考虑把父亲对儿子和儿子对父亲分开考虑（T3也是两个数组dp的）。设f1[i]为i被自己或儿子点亮的概率。f2[i]为i被父亲点亮的概率；那么可以两边dfs分别求解两个数组。
f1[叶子节点]=q[i]；f1[i]=q[i]+
注：这里的加为概率加法，和容斥类似，P(a+b)=P(a)+P(b)-P(a)*P(b);对于i，若直接加，则多加了i即被自己点亮又被儿子点亮的情况。
f2[根节点]=f1[i];设pfa为父亲节点下传的概率，由于f2是有上向下更新，所以f2[fa]已知，pfa=f2[fa]-f1[v]*p()//解释:若fa已经点亮，则有两种情况1.fa被v点亮，2.fa不被v点亮。
所以用fa亮的概率减去fa被v点亮的概率就是fa下传的概率（这里是概率相减，P(A)=(P(A+B)-P(B))/(1-P(B))）。f2[v]=f1[v]+pfa*p();这里也是概率加法，排除v既是自己亮又被fa点亮的情
况。
Ps.还有一种方法记录的是不被点亮的概率，避免了概率的加减（其实我觉得这个也挺好理解的）。
【标程】
#include<iostream>
#include<cstdio>
#include<cmath>
#define esp (1e-13)
using namespace std;
struct edge
{
int u,v,next;double p;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].next
#define p(x) ed[x].p
}ed[1000010];
int first[500010],num_e;
#define f(x) first[x]
int n;
double q[500010];
double f1[500010],f2[500010];
void dfs1(int x,int ff)
{
if(!f(x)){f1[x]=q[x];return;}
f1[x]=q[x];
for(int i=f(x);i;i=n(i))
if(v(i)!=ff)
{
dfs1(v(i),x);
f1[x]=f1[x]+f1[v(i)]*p(i)-f1[x]*f1[v(i)]*p(i);//注
}
}
void dfs2(int x,int ff)
{
double pfa=0;
for(int i=f(x);i;i=n(i))
if(v(i)!=ff)
{
if(fabs((1.0-f1[v(i)]*p(i))<esp))f2[v(i)]=1.0;
else
{
pfa=(f2[x] - f1[v(i)]*p(i))/(1.0-f1[v(i)]*p(i));//注
f2[v(i)]=f1[v(i)]+p(i)*pfa-f1[v(i)]*pfa*p(i);//注
}
dfs2(v(i),x);
}
}
inline void add_e(int u,int v,double p);
signed main()
{
// freopen("in.txt","r",stdin);
cin>>n;
int ta,tb;double tp;
for(int i=1;i<n;i++)
{
scanf("%d%d",&ta,&tb);cin>>tp;tp/=100.0;
add_e(ta,tb,tp);
add_e(tb,ta,tp);
}
for(int i=1;i<=n;i++)
cin>>q[i],q[i]/=100;
dfs1(1,0);
f2[1]=f1[1];
dfs2(1,0);
double ans=0;
for(int i=1;i<=n;i++)
ans+=f2[i];
printf("%0.6lf",ans);
}
inline void add_e(int u,int v,double p)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
p(num_e)=p;
n(num_e)=f(u);
f(u)=num_e;
}
View Code
T3
C. 走迷宫
题目描述
Morenan被困在了一个迷宫里。迷宫可以视为N个点M条边的有向图，其中Morenan处于起点S，迷宫的终点设为T。可惜的是，Morenan非常的脑小，他只会从一个点出发随机沿着一条从该点出发的有向边，到达另一个点。这样，Morenan走的步数可能很长，也可能是无限，更可能到不了终点。若到不了终点，则步数视为无穷大。但你必须想方设法求出Morenan所走步数的期望值。
输入格式
第1行4个整数，N,M,S,T
第[2, M+1]行每行两个整数o1, o2，表示有一条从o1到o2的边。
输出格式
一个浮点数，保留小数点3位，为步数的期望值。若期望值为无穷大，则输出"INF"。
样例
样例输入1
6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6样例输出1
3.000样例输入2
9 12 1 9
1 2
2 3
3 1
3 4
3 7
4 5
5 6
6 4
6 7
7 8
8 9
9 7样例输出2
9.500样例输入3
2 0 1 2样例输出3
INF数据范围与提示
| 测试点 | N | M | Hint |
|---|---|---|---|
| [1, 6] | <=10 | <=100 | |
| [7, 12] | <=200 | <=10000 | |
| [13, 20] | <=10000 | <=1000000 | 保证强连通分量的大小不超过100 |
另外，均匀分布着40%的数据，图中没有环，也没有自环
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#define esp 1e-13
using namespace std;
struct edge
{
int u,v,next;
#define uz(x) ed[x].u
#define vz(x) ed[x].v
#define nz(x) ed[x].next
#define uf(x) edf[x].u
#define vf(x) edf[x].v
#define nf(x) edf[x].next
}ed[2000100],edf[2000100];
int first[10010],num_e,firstf[10010],num_ef;
#define fz(x) first[x]
#define ff(x) firstf[x]
int n,m,S,T;
double ru[10010],cu[10010];
double f[10010];
double a[3010][3010],b[10010],c[10010];
int dis[10010];bool vi[10010];
void spfa(int st)
{
for(int i=0;i<=n;i++)dis[i]=0x7fffffff;
dis[st]=0;
vi[st]=1;
queue<int> que;
que.push(st);
int k;
while(!que.empty())
{
k=que.front();
que.pop();
vi[k]=0;
for(int i=fz(k);i;i=nz(i))
if(dis[k]+1<dis[vz(i)])
{
dis[vz(i)]=dis[k]+1;
if(!vi[vz(i)])
{
vi[vz(i)]=1;
que.push(vz(i));
}
}
}
}
inline void gs();
inline void add_e(int u,int v);
inline void add_ef(int u,int v);
int main()
{
// freopen("in.txt","r",stdin);
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
cin>>n>>m>>S>>T;
if(S==T){printf("%0.3lf",0.000);return 0;}
if(m==0){cout<<"INF";return 0;}
int ta,tb;
for(int i=1;i<=m;i++)
{
cin>>ta>>tb;
if(ta!=T)
{
add_e(ta,tb);
add_ef(tb,ta);
ru[tb]++;cu[ta]++;
}
}
spfa(S);
if(dis[T]==0x7fffffff)
{cout<<"INF";return 0;}
for(int i=1;i<=n;i++)
{
a[i][i]=1;
for(int j=ff(i);j;j=nf(j))
{
a[i][vf(j)]-=1/(cu[vf(j)]);
}
}
b[1]=1;
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }cout<<endl;
gs();
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }cout<<endl;
double ans=0;
for(int i=1;i<=n;i++)
ans+=c[i];
printf("%0.3lf",(ans-1));
return 0;
}
inline void gs()
{
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
if(fabs(a[j][i])>fabs(a[i][i]))
{
for(int k=1;k<=n;k++)
swap(a[j][k],a[i][i]);
swap(b[j],b[i]);
}
for(int j=1;j<=n;j++)
{
if(j==i)continue;
if(fabs(a[i][i])<=esp)continue;
double rate=a[j][i]/a[i][i];
for(int k=1;k<=n;k++)
a[j][k]-=a[i][k]*rate;
b[j]-=b[i]*rate;
}
}
for(int i=1;i<=n;i++)
c[i]=b[i]/a[i][i];
}
inline void add_e(int u,int v)
{
++num_e;
uz(num_e)=u;
vz(num_e)=v;
nz(num_e)=fz(u);
fz(u)=num_e;
}
inline void add_ef(int u,int v)
{
++num_ef;
uf(num_ef)=u;
vf(num_ef)=v;
nf(num_ef)=ff(u);
ff(u)=num_ef;
}
暴力RE50
这个题是比较容易拿分的，但是AC就比较难了。考试的时候主要是题意没有理解。按游走的思路打高斯消元能拿50分（据说有人拿了60...），更水的是直接输出INF能拿20...然后是我没有理解的题意:
对于无穷大的情况，我打了spfa判断，但气死spfa只能判出来一个点，题中说的无穷大不只是起点与终点不连通，如图，当从S走到1时，就无法到达终点，此时步数为INF，那么ans+=概率*INF，ans=INF；此时答案必定为INF。
然后我就想，如果INF*概率=INF的话，S123123...这种情况的步数也是无穷大，那岂不是不能有环？其实并不是这样的，无限≠无穷大，如果是环的话，虽然步数在无限增大，但概率也在无限减少，就比如，这种情 况高斯消元就直接处理了。
【题解】
数据范围已经提示了强连通分量，所以肯定要缩点（考试想到了，但因为不会打tarjan就没继续想），强连通分量的大小不超过100，所以考虑对于每个scc高斯消元。
题中问的是期望步数，显然期望步数=（点的期望经过次数）-1。所以设f[i]为i点的期望经过次数，和第二个题一样，因为每个scc要受其他scc影响，所以用另外一个数组辅助dp，设g[i]为其他scc到的期望次数。f[i]=g[i]+∑（f[j]/cu[j]），边界：起点的期望步数初始值为一，所以令g[S]=1即可。同样因为scc之间的相互影响，要按拓扑序进行高斯消元，对于入度是0的scc，直接高斯消元即可，对于每个scc，高斯消元之后更新与之相连的点的g。因为是按拓扑序，所以更新到一个scc是，这个scc中每个点的g值都已更新。
然后是INF的判断，如果除belong[T]外有scc的出度为0，那么这个scc无法到达T，期望为INF。
Ps.因为是按拓扑序正序更新，所以要注意这种情况，入度为0的scc可能不只有一个。也有其他题解是拓扑序倒序更新，就避免了这种情况。
【标程】
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#define esp (1e-13)
using namespace std;
struct edge
{
int u,v,next;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].next
#define uf(x) edf[x].u
#define vf(x) edf[x].v
#define nf(x) edf[x].next
}ed[2000100],edf[2000100];
int first[10010],num_e,firstf[10010],num_f;
#define f(x) first[x]
#define ff(x) firstf[x]
int n,m,S,T;
int cu[10010],ru[10010],cud[10010];
double f[10010],g[10010];
int dfn[10010],low[10010],belong[10010],num,tot;
bool vi[10010];
int stack[10010],top;
vector<int> scc[10010];
double a[110][110],b[110];
bool vv[10010];
void gs(int nn);
void tarjan(int x);
inline void add_e(int u,int v);
inline void add_f(int u,int v);
signed main()
{
// freopen("14.in","r",stdin);
cin>>n>>m>>S>>T;
int fr,to;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&fr,&to);
if(fr!=T)
{
add_e(fr,to),
cud[fr]++,
add_f(to,fr);
}
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=tot;++i)
for(int j=0;j<scc[i].size();++j)
for(int k=ff(scc[i][j]);k;k=nf(k))
if(belong[vf(k)]!=i )
ru[i]++,
cu[belong[vf(k)]]++;
for(int i=1;i<=tot;i++)
if(i!=belong[T] && cu[i]==0)
{cout<<"INF";return 0;}
g[S]=1;
queue<int> tem;
for(int i=1;i<=tot;i++)
if(ru[i]==0)tem.push(i);
int k;
while(!tem.empty())
{
k=tem.front();
tem.pop();
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<scc[k].size();i++)
{
int t1=scc[k][i];
a[i+1][i+1]=1;
b[i+1]=g[scc[k][i]];
for(int j=ff(scc[k][i]);j;j=nf(j))
if(belong[vf(j)]==belong[scc[k][i]])
{
int q=0;
for(q=0;q<scc[k].size();q++)
if(scc[k][q]==vf(j))break;
a[i+1][q+1]-=(double)1/(double)cud[vf(j)];
}
}
gs(scc[k].size());
for(int i=0;i<scc[k].size();i++)
{
int tt=scc[k][i];
f[tt]=b[i+1]/a[i+1][i+1];
for(int j=f(tt);j;j=n(j))
if(belong[v(j)]!=belong[tt])
{
g[v(j)]+=f[tt]/(double)cud[tt];
ru[belong[v(j)]]--;
if(ru[belong[v(j)]]==0)tem.push(belong[v(j)]);
}
}
}
f[T]=1;
double ans=0;
for(int i=1;i<=n;i++)
ans+=f[i];
printf("%0.3lf",ans-1);
}
void gs(int nn)
{
for(int i=1;i<=nn;i++)
{
for(int j=i;j<=nn;j++)
if(fabs(a[j][i])>fabs(a[i][i]))
{
for(int k=1;k<=nn;k++)
swap(a[i][k],a[j][k]);
swap(b[i],b[j]);
}
for(int j=1;j<=nn;j++)
{
if(j==i)continue;
if(fabs(a[i][i])<=esp)continue;
double rate=a[j][i]/a[i][i];
for(int k=1;k<=nn;k++)
a[j][k]-=rate*a[i][k];
b[j]-=b[i]*rate;
}
}
}
inline void add_f(int u,int v)
{
++num_f;
uf(num_f)=u;
vf(num_f)=v;
nf(num_f)=ff(u);
ff(u)=num_f;
}
inline void add_e(int u,int v)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
n(num_e)=f(u);
f(u)=num_e;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
stack[++top]=x;vi[x]=1;
for(int i=f(x);i;i=n(i))
if(!dfn[v(i)]) tarjan(v(i)),low[x]=min(low[x],low[v(i)]);
else if(vi[v(i)]) low[x]=min(low[x],low[v(i)]);
if(dfn[x]==low[x])
{
++tot;vi[x]=0;
while(stack[top]!=x)
{
vi[stack[top]]=0;
scc[tot].push_back(stack[top]);
belong[stack[top--]]=tot;
}
scc[tot].push_back(stack[top]);
belong[stack[top--]]=tot;
}
}
View Code
这次考试最大的收获就是T2和T3的两个数组dp，自己做的话是比较难想到的，当dp相互影响难以实现时，考虑一下将状态分开考虑。