您当前的位置: 首页 > 

minato_yukina

暂无认证

  • 4浏览

    0关注

    138博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

P2194 HXY烧情侣

minato_yukina 发布时间:2022-09-10 16:29:44 ,浏览量:4

在这里插入图片描述 思路:纯纯阅读理解题,它这个去电影院不是沿着道路走的,也就是不需要按照图的顺序访问,是直接挑选一个 s c c scc scc去访问 那问题就很好解决了,对于一个强联通块,必须访问他们的最少的点权的点,设为 n u m [ x ] num[x] num[x]. 方案数目就是 ∏ n u m [ x ] \prod num[x] ∏num[x] 对了,它是方案数取模,其他不取模,注意

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
int dfn[maxn],low[maxn],dfs_clock=0;int scc[maxn],scc_cnt;
stack S;
int mn[maxn],num[maxn];int a[maxn];
void dfs(int u){
	low[u] = dfn[u] = ++dfs_clock;
	S.push(u);
	for(auto v : G[u]){
		if(!dfn[v]){
			dfs(v);
			low[u] = min(low[u],low[v]);
		}
		else if(!scc[v]) low[u] = min(low[u],dfn[v]);//不是cross_edge而是back_edge的情况更新
	}
	if(low[u]==dfn[u]){
		scc_cnt++;
		while(true){
			int x=S.top();S.pop();
			if(a[x]>n;
	for(int i=1;i>a[i];mn[i] = INF;
	}
	int m;cin>>m;
	for(int i=1;i>u>>v;
		G[u].pb(v);
	}
	for(int i=1;i            
关注
打赏
1663570241
查看更多评论
0.6873s