正題

題目鏈接:https://www.luogu.com.cn/problem/P7293

---

題目大意

有$k$張聯(lián)通無向圖，有$k$個人從每張圖的點$1$出發(fā)，定義所有人的位置合為一個狀態(tài)，求初始狀態(tài)到達(dá)所有能到達(dá)狀態(tài)的最短時間的和。

輸出答案對 $10^9+7$ 取模。

$\sum n\le 10^5,\sum m\le 2\times 10^5$

---

解題思路

因為可以反復(fù)橫跳，對于每個點我們求出到達(dá)的最短的奇數(shù)/偶數(shù)距離，記為$dis1/dis2$。

那么對于一個狀態(tài)$(i_1,i_2,...,i_n)$答案就是
$$\min \{\max \{dis{1}_{i_j}\},\max \{dis{2}_{i,j}\}\}$$

然后這個又有$\min$又有$\max$的很難搞，但是我們有一個式子$a+b=\max \{a,b\}+\min \{a,b\}$（好像很廢話），然后就有$\min \{a,b\}=a+b?\max \{a,b\}$，這樣就把$\max$消掉了。

那么答案有
$$\max \{dis{1}_{i_j}\}+\max \{dis{2}_{i_j}\}?\max \{dis{1}_{i_j},dis{2}_{i_j}\}$$

然后跑出$dis1,dis2$排個序就很好統(tǒng)計了。

注意不能統(tǒng)計上無法達(dá)到的狀態(tài)。

時間復(fù)雜度：$O(N\log N+M)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define mp(x,y) make_pair(x,y) #define ll long long using namespace std; const ll N=2e5+10,P=1e9+7; struct node{ll to,next; }a[N<<2]; ll k,n,m,ans,tot,ls[N],c[N],dis[N]; vector<pair<ll,ll> >b[3]; queue<ll> q; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void bfs(){q.push(1);dis[1]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dis[y]<=dis[x]+1)continue;dis[y]=dis[x]+1;q.push(y);}}return; } void calc(ll id,ll op){ll res=0,now=0;memset(c,0,sizeof(c));for(ll i=0;i<b[id].size();i++){ll d=b[id][i].first,p=b[id][i].second;if(d+1>=dis[0])break;now+=!c[p];c[p]++;ll invn=power(c[p],P-2);if(now==k){res=1;for(int i=1;i<=k;i++)res=res*c[i]%P;}res=res*invn%P;(ans+=res*d*op%P)%=P;res=res*c[p]%P;}return; } signed main() {scanf("%lld",&k);for(ll i=0;i<N;i++)dis[i]=2147483647;for(ll p=1;p<=k;p++){scanf("%lld%lld",&n,&m);for(ll i=1,x,y;i<=m;i++){scanf("%lld%lld",&x,&y);addl(x,y+n);addl(x+n,y);addl(y,x+n);addl(y+n,x);}bfs();for(ll i=1;i<=n;i++){b[0].push_back(mp(dis[i]-1,p));b[1].push_back(mp(dis[i+n]-1,p));b[2].push_back(mp(max(dis[i],dis[i+n])-1,p));}for(ll i=1;i<=2*n;i++)ls[i]=0,dis[i]=dis[0];tot=0;}sort(b[0].begin(),b[0].end());sort(b[1].begin(),b[1].end());sort(b[2].begin(),b[2].end());calc(0,1);calc(1,1);calc(2,-1);printf("%lld\n",(ans+P)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7293-[USACO21JAN]Sum of Distances P【统计,bfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。