网站名字备案,WordPress重新安装删除哪个,怎么做赌钱网站代理,企业管理信息系统网站文章目录题目描述解析代码题目描述 解析
乍一看#xff1a;是个水题啊#xff01; 显然如果途径存在强连通的点#xff0c;路径就会变为正无穷 所以缩点加拓扑dp以及一些特判应该就可以解决了#xff01; 一交#xff1a;40分。。。 然后就开始拆东墙补西墙的debug。。。…
文章目录题目描述解析代码题目描述 解析
乍一看是个水题啊 显然如果途径存在强连通的点路径就会变为正无穷 所以缩点加拓扑dp以及一些特判应该就可以解决了 一交40分。。。 然后就开始拆东墙补西墙的debug。。。 de到80之后实在无计可施看了测试数据 最终在交了10余次后切掉了本题泪目 总结一下遇见的问题吧 1.是所以超过36500的点视为相等而不是有超过36500的点就全部认为相等gg省选的亏还是没吃够啊。。。 2.判断强连通特判的位置应该在topu的while大循环的里面而不是判断出边的地方如果这里不像人话可以看下面的代码有注释说明否则入度为0的强连通会统计不上 3.有自环路径也相当于正无穷就是这个地方卡80分一直没想到以后要培养题里没说没有就要考虑自环、重复路径的思维 4.在2的判断的位置不是所有有自环的或强连通都是可以的至少。。它得能走到n1点啊。。。 总的来说本题是一道考验严谨思维的题数据出的很好提升了本题的质量 我也要提升自己的质量
代码
#includebits/stdc.h
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N2e6100;
const int M2e6100;
const int X36500;
int n,m;
int cnt-1,fi[N];
struct node{int to,nxt;
}p[M];
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
int a,b;
int zhan[N],dfs[N],low[N],col[N];
int ed,tot,tim;
int size[N];
int self[N];
void tarjan(int x){zhan[ed]x;dfs[x]low[x]tim;for(int ifi[x];~i;ip[i].nxt){int up[i].to;if(dfs[u]0){tarjan(u);low[x]min(low[x],low[u]);}else if(col[u]0) low[x]min(low[x],low[u]);}if(low[x]dfs[x]){col[x]tot;size[tot]1;if(self[x]) self[tot]1;while(zhan[ed]!x){if(self[zhan[ed]]) self[tot]1;col[zhan[ed--]]tot;size[tot];}ed--;}
}
int flag,dp[N],ru[N];
void topu(){queueintq;for(int in1;itot;i) if(ru[i]0) q.push(i);while(!q.empty()){int nowq.front();q.pop();
// printf(now%d\n,now);if(self[now]dp[now]||dp[now]X||(dp[now]size[now]!1)){dp[now]36501;}//刚才第二条说的就是上面的这个特判不能写在下面的A处for(int ifi[now];~i;ip[i].nxt){int up[i].to;//A处就是这里啦
// printf(now%d to%d\n,now,u);dp[u]dp[now];if(--ru[u]0){q.push(u);}}}
}
int ans,num,jd[N];
int main(){scanf(%d%d,n,m);n;totn;mem(fi,-1);for(int i1;im;i){scanf(%d%d,a,b);if(ab) self[a]1;else addline(b,a);//反向建图 }for(int i1;in;i){if(!dfs[i]) tarjan(i);}for(int i1;in;i){int xxcol[i];for(int jfi[i];~j;jp[j].nxt){int yycol[p[j].to];if(xx!yy){addline(xx,yy);ru[yy];}}}
// for(int i1;in1;i) printf(i%d col%d size%d\n,i,col[i],size[col[i]]);dp[col[n]]1;topu();
// for(int i1;in;i) printf(i%d dp%d\n,i,dp[col[i]]); for(int in1;itot;i){if(dp[i]36500){flag1,ans36501;break;}else ansmax(ans,dp[i]);}for(int in1;itot;i){if(dp[i]ans){numsize[i];jd[i]1;}}if(ans36500) printf(%d\n,ans);else printf(zawsze\n);printf(%d\n,num);for(int i1;in;i){if(jd[col[i]]) printf(%d ,i);}return 0;
}
/*
3 2
3 4
4 3
*/
