社区讨论
缩点+dij最短路,29ptsWA求助,真没找到错哪QAQ
P3119[USACO15JAN] Grass Cownoisseur G参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo2ichcr
- 此快照首次捕获于
- 2023/10/23 14:19 2 年前
- 此快照最后确认于
- 2023/10/23 14:19 2 年前
CPP
#include<bits/stdc++.h>
#define N 100004
using namespace std;
int n,m,cnt,cc,cs,ans;
struct side{
int u,v;
}sd[N];
vector<int>g[N],g_[N],h_[N];
int dfn[N],low[N],col[N],val[N];
stack<int>s;
bool ins[N];
int d1[N],d2[N];
bool f1[N],f2[N];
inline int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch&15);
ch=getchar();
}
return x;
}
void tarjan(int u){
dfn[u]=low[u]=++cnt;
ins[u]=1,s.push(u);
for(int v:g[u]){
if(dfn[v]){
if(ins[v])low[u]=min(low[u],dfn[v]);
}
else{
tarjan(v);
low[u]=min(low[u],low[v]);
}
}
if(dfn[u]==low[u]){
cc++;
int x;
while(1){
x=s.top();
col[x]=cc;
val[cc]++;
ins[x]=0;
s.pop();
if(x==u)break;
}
}
}
struct node{
int v,w;
};
bool operator<(const node &x,const node &y){
return x.w<y.w;
}
void dij(vector<int>g[],int dis[],bool f[]){
priority_queue<node>q;
int u=col[1];
dis[u]=val[u];
q.push({u,dis[u]});
while(!q.empty()){
u=q.top().v;
q.pop();
if(f[u])continue;
f[u]=1;
for(int v:g[u]){
if(dis[v]<dis[u]+val[v]){
dis[v]=dis[u]+val[v];
q.push({v,dis[v]});
}
}
}
}
int main(){
memset(d1,-63,sizeof(d1));
memset(d2,-63,sizeof(d2));
int u,v;
n=read(),m=read();
for(int i=1;i<=m;i++){
u=read(),v=read();
g[u].push_back(v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
#define u col[i]
#define v col[j]
for(int i=1;i<=n;i++)
for(int j:g[i])
if(u!=v){
g_[u].push_back(v);
h_[v].push_back(u);
sd[++cs]={v,u};
}
#undef u
#undef v
dij(g_,d1,f1),dij(h_,d2,f2);
ans=val[col[1]];//不逆向
for(int i=1;i<=cs;i++)
ans=max(ans,d1[sd[i].u]+d2[sd[i].v]-val[col[1]]);
printf("%d",ans);
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...