USACO 2021 January Contest, Platinum Problem 1. Sum of Distances 铂金组T1

本文主要是介绍USACO 2021 January Contest, Platinum Problem 1. Sum of Distances 铂金组T1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

USACO 2021 January Contest, Platinum Problem 1. Sum of Distances 铂金组T1

题意概述
给出K张图，设K元组，（1，1，1，1，……，1）出发，（a1,a2,a3,……,ak）与（b1,b2,b3,……,bk）有边当且仅当a1与b1,a2与b2，……，ak与bk均有边连接
求出发可到达的距离和

solution
对于多元组a1-ak，认为是第i张图从1走到ai，假如某几张图比其他图更早到达，则可以通过在某条边上反复横跳来等待其他图到达，所以多元组内奇偶性相同，则可以分别求出奇偶最短路，再用奇偶方案相加再减去同时的方案，现在考虑统计答案，我们枚举最短路的值域，由于最短路的长度不会超过节点数，再枚举每个值有哪几张图，乘上它的出现次数，假如图第一次出现就增加计数，否则就除以上一次出现时乘的数，假如所有图都出现过后统计答案，答案乘以当前最短路值，因为对于长度为i的最短路来说，方案数为其他图小于等于i的方案数

#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define mo 1000000007
using namespace std;
int K,g[N][3],inv[N],add[N];
basic_string<int> w[3][N+5];
int getans(basic_string<int> *w){int cnt=0,res=0,t=1;memset(add,0,sizeof add);for(int i=0;i<N;++i){for(int j:w[i]){if(add[j])t=1ll*t*inv[add[j]]%mo;else++cnt;if(cnt==K){res=(res+1ll*t*i)%mo;}t=1ll*t*(++add[j])%mo;}}return res;
}
int main(){inv[1]=1;for (int i=2;i<=N;++i) {inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;}scanf("%d",&K);for(int o=1;o<=K;++o){int n,m;basic_string<int> odd,even;vector<basic_string<int> > t;queue< pair<int,bool> > que;scanf("%d%d",&n,&m);odd.assign(n+1,N),even.assign(n+1,N),t.resize(n+1);for(int i=1,u,v;i<=m;++i){scanf("%d%d",&u,&v);t[u]+=v,t[v]+=u;}que.push({1,0});even[1]=0;while(!que.empty()){pair<int,bool> i=que.front();que.pop();if(i.second){for(int j:t[i.first]){if(even[j]==N)even[j]=odd[i.first]+1,que.push({j,0});}}elsefor(int j:t[i.first]){if(odd[j]==N)odd[j]=even[i.first]+1,que.push({j,1});}}for(int i=1;i<=n;++i){w[0][odd[i]]+=o,w[1][even[i]]+=o,w[2][max(even[i],odd[i])]+=o;}}printf("%d",((getans(w[0])+getans(w[1])-getans(w[2]))%mo+mo)%mo);
}

这篇关于USACO 2021 January Contest, Platinum Problem 1. Sum of Distances 铂金组T1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---