有草鉴定例题 代码详细注释,文字说明易懂
首先看一眼,是单向边。。。
我们要求最多能达到的草场数,而又有可以COW可以违反规定,自然而然的想到分层图,然而我们如何的保证跑出来的是最长路,而且走过的操场不重复,我们自然的想到tarjan缩点,这样保证了新图是一个DAG,这样再进行分层图复制,这样可以保证没有正权环(他就无环),然后跑一边spfa即可
这题其实挺考码力的(猪国杀笑了)
我们来理清思路,最重要的是分步来实现
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int Maxn=1e5+11;
int n,m,x,y,h[Maxn*2],cnt,p[2*Maxn],dis[Maxn*2];
bool fsta[Maxn],vis[Maxn*2];
struct Edge{
int fr,to,lac;
}edge[Maxn*3],vedge[Maxn];
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x;
}
void insert(int y,int x){
edge[cnt].to=y;
edge[cnt].fr=x;
edge[cnt].lac=h[x];
h[x]=cnt++;
}
int low[Maxn],dfn[Maxn],dep,sta[Maxn],top,col[Maxn],num;
void tarjan(int u){
low[u]=dfn[u]=++dep;
fsta[u]=1,sta[++top]=u;
for(int i=h[u];i!=-1;i=edge[i].lac){
int to=edge[i].to;
if(dfn[to]){
if(fsta[to]) low[u]=min(low[u],dfn[to]);
continue;
}
tarjan(to);
low[u]=min(low[u],low[to]);
}
if(low[u]==dfn[u]){
num++;
while(fsta[u]){
col[sta[top]]=num;
fsta[sta[top--]]=0;
}
}
}
bool spe(){
if(num==1){
printf("%d",n);
return 0;
}
return 1;
}
void dijkstra(){
queue<int> que;//这真的是spfa
que.push(col[1]);
while(!que.empty()){
int fr=que.front();
que.pop();
vis[fr]=0;
for(int i=h[fr];i!=-1;i=edge[i].lac){
int to=edge[i].to;
if(dis[to]<dis[fr]+p[to]){
dis[to]=dis[fr]+p[to];//其实再DAG里,点权可以当边权用了
if(!vis[to]){
vis[to]=1;
que.push(to);
}
}
}
}
return;
}
int main(){
// freopen("Grass.in","r",stdin);
n=read(),m=read();
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++) insert(read(),read());
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
if(spe()){//特判只有一个强连通如果不的话,我们没有边。。
memset(h,-1,sizeof h);
memcpy(vedge,edge,sizeof vedge);
cnt=0;
for(int i=0;i<m;i++){
int fr=vedge[i].fr,to=vedge[i].to;
if(col[fr]==col[to]) continue;
insert(col[to],col[fr]);
}//建第一层
for(int i=0;i<m;i++){
int fr=vedge[i].fr,to=vedge[i].to;
if(col[fr]==col[to]) continue;
insert(col[to]+num,col[fr]+num);
}//建第二层
for(int i=0;i<m;i++){
int fr=vedge[i].fr,to=vedge[i].to;
if(col[fr]==col[to]) continue;
insert(col[fr]+num,col[to]);
}//连接一二层
for(int i=1;i<=n;i++) p[col[i]]++;
for(int i=1;i<=num;i++) p[num+i]=p[i];
dijkstra();//spfa......
printf("%d",dis[num+col[1]]);//输出最长路
}
return 0;
}
flag:第二版会补充JLOI 的飞行计划,本周就会有第二版,或许有第三版
原文:https://www.cnblogs.com/zhltao/p/12293466.html