P2194 HXY烧情侣

本文主要是介绍P2194 HXY烧情侣，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

~~~~~      P2194 HXY烧情侣 ~~~~~      总题单链接

思路

~~~~~      缩点，求每个强连通分量的最小权值，记录有几个点的权值是最小权值。

~~~~~      最少费用就是每个强连通分量最小权值的和。

~~~~~      方案数就是每个强连通分量最小权值的点的个数的积。

代码

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;ll n,m,a[100005];
vector<ll>eg[100005];
ll dfn[100005],low[100005],tot;
ll stk[100005],init[100005],top;
ll scc[100005],mi[100005],mk[100005],cnt;void Tarjan(ll p){dfn[p]=low[p]=++tot;stk[++top]=p;init[p]=1;for(ll v:eg[p]){if(!dfn[v]){Tarjan(v);low[p]=min(low[p],low[v]);}else if(init[v])low[p]=min(low[p],dfn[v]);}if(dfn[p]==low[p]){cnt++;while(1){ll v=stk[top--];scc[v]=cnt;init[v]=0;if(a[v]<mi[cnt])mi[cnt]=a[v],mk[cnt]=1;else if(a[v]==mi[cnt])mk[cnt]++;if(v==p)break;}}
}signed main(){ios::sync_with_stdio(false);memset(mi,0x3f,sizeof(mi));cin>>n;for(ll i=1;i<=n;i++)cin>>a[i];cin>>m;while(m--){ll x,y;cin>>x>>y;eg[x].push_back(y);}for(ll i=1;i<=n;i++)if(!dfn[i])Tarjan(i);ll k1=0,k2=1;for(ll i=1;i<=cnt;i++){k1+=mi[i];(k2*=mk[i])%=MOD;}cout<<k1<<" "<<k2;return 0;
}

这篇关于P2194 HXY烧情侣的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---