生活随笔
收集整理的這篇文章主要介紹了
洛谷P3119
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
省選難度啊啊啊
經評論區的朋友提醒，代碼已訂正
先說一下該題思路:
首先,這題并非是求最短路,而是求最長路(最長路常用算法一般是拓撲排序,而我這個蒟蒻還沒有學會QAQ)
但是這一題既然標簽是連通圖,那么肯定要用tarjan,考慮到縮點之后每個縮點都具有一定數量的點數,然后如果我們進入了這個縮點,那么我們可以從進入該縮點的點起,然后將整個縮點中的點全部遍歷一遍,所以我們可以將縮點中的點數作為邊的權值(既然有權值那么我們就可以跑spfa),進行縮點之后就可以重新建圖,所以在這里我們有三個first,nxt,v,然后我們要跑兩邊spfa,所以我們要有兩個dis數組來保存正向和逆向的距離,然后只需要枚舉每個點,同時用最大值來更新ans
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
using namespace std
;
const int maxn
=100003;
stack
<int> s
;
queue
<int> 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 to
=first
[x
];to
!=-1;to
=nxt
[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{k
=s
.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 k
=q
.front();q
.pop();for(int to
=f1
[k
];to
!=-1;to
=nxt1
[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 k
=q
.front();q
.pop();for(int to
=f2
[k
];to
!=-1;to
=nxt2
[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
;cin
>>n
>>m
;memset(first
,-1,sizeof(first
));memset(f1
,-1,sizeof(f1
));memset(f2
,-1,sizeof(f2
));for(int k
=0;k
<m
;k
++){scanf("%d%d",&a
,&b
);add(a
,b
);}for(int i
=1;i
<=n
;i
++)if(!dfn
[i
])tarjan(i
);start
=c
[1];for(int i
=1;i
<=n
;i
++)for(int to
=first
[i
];to
!=-1;to
=nxt
[to
])if(c
[i
]!=c
[v
[to
]]){add1(c
[i
],c
[v
[to
]]);add2(c
[v
[to
]],c
[i
]);}spfa1(start
);spfa2(start
);int ans
=cnt
[start
];for(int i
=1;i
<=n
;i
++)if(!use
[c
[i
]] && dis1
[c
[i
]]){use
[c
[i
]]=1;for(int to
=f2
[c
[i
]];to
!=-1;to
=nxt2
[to
]){if(!dis2
[v2
[to
]])continue;ans
=max(dis1
[c
[i
]]+dis2
[v2
[to
]]-cnt
[start
],ans
);}}cout
<<ans
;return 0;
}
好像說了這么久,應該只有我自己一個人懂吧233333
另一個神犇的分層法暫時還沒懂23333
總結
以上是生活随笔為你收集整理的洛谷P3119的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
