推广网站的方法有,北京西城网站建设公司,网页设计与制作工资多少,wordpress redis缓存定时省选难度啊啊啊 经评论区的朋友提醒#xff0c;代码已订正 先说一下该题思路: 首先,这题并非是求最短路,而是求最长路(最长路常用算法一般是拓扑排序,而我这个蒟蒻还没有学会QAQ) 但是这一题既然标签是连通图,那么肯定要用tarjan,考虑到缩点之后每个缩点都具有一定数量的点数,…省选难度啊啊啊 经评论区的朋友提醒代码已订正 先说一下该题思路: 首先,这题并非是求最短路,而是求最长路(最长路常用算法一般是拓扑排序,而我这个蒟蒻还没有学会QAQ) 但是这一题既然标签是连通图,那么肯定要用tarjan,考虑到缩点之后每个缩点都具有一定数量的点数,然后如果我们进入了这个缩点,那么我们可以从进入该缩点的点起,然后将整个缩点中的点全部遍历一遍,所以我们可以将缩点中的点数作为边的权值(既然有权值那么我们就可以跑spfa),进行缩点之后就可以重新建图,所以在这里我们有三个first,nxt,v,然后我们要跑两边spfa,所以我们要有两个dis数组来保存正向和逆向的距离,然后只需要枚举每个点,同时用最大值来更新ans
#includeiostream
#includecstdio
#includecstring
#includestack
#includequeue
using namespace std;
const int maxn100003;
stackint s;
queueint q;
int tot,tot1,tot2;
int v[maxn],v1[maxn],v2[maxn];
int nxt[maxn],nxt1[maxn],nxt2[maxn];
int first[maxn],f1[maxn],f2[maxn];
int ins[maxn],dfn[maxn],low[maxn];
int c[maxn],cnt[maxn],use[maxn];
int dis1[maxn],dis2[maxn];
int timing,col;
void add(int x,int y)
{v[tot]y;nxt[tot]first[x];first[x]tot;
}
void add1(int x,int y)
{v1[tot1]y;nxt1[tot1]f1[x];f1[x]tot1;
}
void add2(int x,int y)
{v2[tot2]y;nxt2[tot2]f2[x];f2[x]tot2;
}
void tarjan(int x)
{ins[x]1;s.push(x);dfn[x]low[x]timing;for(int tofirst[x];to!-1;tonxt[to]){if(!dfn[v[to]]){tarjan(v[to]);low[x]min(low[x],low[v[to]]);}else if(ins[v[to]])low[x]min(low[x],low[v[to]]);}if(dfn[x]low[x]){col;int k;do{ks.top();ins[k]0;c[k]col;cnt[col];s.pop();} while (k!x);}
}
void spfa1(int x)
{dis1[x]cnt[x];q.push(x);while(!q.empty()){int kq.front();q.pop();for(int tof1[k];to!-1;tonxt1[to]){if(dis1[v1[to]]dis1[k]cnt[v1[to]])dis1[v1[to]]dis1[k]cnt[v1[to]];if(!ins[v1[to]]){q.push(v1[to]);ins[v1[to]]1;}}ins[k]0;}
}
void spfa2(int x)
{dis2[x]cnt[x];q.push(x);while(!q.empty()){int kq.front();q.pop();for(int tof2[k];to!-1;tonxt2[to]){if(dis2[v2[to]]dis2[k]cnt[v2[to]])dis2[v2[to]]dis2[k]cnt[v2[to]];if(!ins[v2[to]]){q.push(v2[to]);ins[v2[to]]1;}}ins[k]0;}
}
int main()
{int n,m,a,b,start;cinnm;memset(first,-1,sizeof(first));memset(f1,-1,sizeof(f1));memset(f2,-1,sizeof(f2));for(int k0;km;k){scanf(%d%d,a,b);add(a,b);}for(int i1;in;i)if(!dfn[i])tarjan(i);startc[1];for(int i1;in;i)for(int tofirst[i];to!-1;tonxt[to])if(c[i]!c[v[to]]){add1(c[i],c[v[to]]);add2(c[v[to]],c[i]);}spfa1(start);spfa2(start);int anscnt[start];for(int i1;in;i)if(!use[c[i]] dis1[c[i]]){use[c[i]]1;for(int tof2[c[i]];to!-1;tonxt2[to]){if(!dis2[v2[to]])continue;ansmax(dis1[c[i]]dis2[v2[to]]-cnt[start],ans);}}coutans;return 0;
}好像说了这么久,应该只有我自己一个人懂吧233333
另一个神犇的分层法暂时还没懂23333
