C++14(g++5.4) 解法, 执行用时: 836ms, 内存消耗: 28324K, 提交时间: 2020-01-24 17:06:48
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int sub(int x, int y) {
x -= y;
return x < 0 ? x + mod : x;
}
int add(int x, int y) {
x += y;
return x >= mod ? x - mod : x;
}
int mul(int x, int y){
return 1ll * x * y % mod;
}
ll calc(ll x, ll y){
ll z = 1;
while (y) {
if (y & 1) z = z * x % mod;
x = x * x % mod, y /= 2;
}
return z;
}
int det(vector< vector<int> > f) {//模数是质数
int n = f.size();
int ans = 1;
for (int i = 0 ; i < n; i ++) {
if (!f[i][i]) {
for (int j = i + 1; j < n; j ++)
if (f[j][i]) {
swap(f[i], f[j]);
ans = (mod - ans) % mod;
break;
}
}
if (!f[i][i])
return 0;
int niv = calc(f[i][i], mod - 2);
for (int j = i + 1; j < n; j ++)
if (f[j][i]) {
int v = 1ll * niv * f[j][i] % mod;
for (int k = i; k < n; k ++)
f[j][k] = (f[j][k] - 1ll * v * f[i][k] % mod + mod) % mod;
}
ans = (mod + 1ll * ans * f[i][i]) % mod;
}
return ans;
}
const int N = 2e5 + 10;
vector<int> g[N];
vector<pair<int, int> > edge, edge1[N];
int fa[N];
int belong[N], deep[N], id[N];
int tot;
int n,m;
bool bz[N];
int ans = 0;
int getfa(int x) {
return fa[x] == x ? x : fa[x] =getfa(fa[x]);
}
void dfs(int x, int fa) {
if (bz[x]) {
id[belong[x] = ++tot] = x;
}
deep[x] ++;
int sum = 0;
for (auto u:g[x])
if (u!=fa) {
deep[u] = deep[x];
dfs(u, x);
sum += (belong[u] > 0);
}
if (!belong[x]) {
if (sum == 1) {
for (auto u:g[x])
if (u!=fa && belong[u])
belong[x] = belong[u];
} else
if (sum > 1)
id[belong[x] = ++tot] = x;
}
if (belong[x])
for (auto u:g[x])
if (u!=fa && belong[u] && belong[u] != belong[x])
edge1[belong[u]].push_back(make_pair(belong[x], deep[id[belong[u]]] - deep[x])), edge1[belong[x]].push_back(make_pair(belong[u], deep[id[belong[u]]] - deep[x]));
}
//#include <assert.h>
int main() {
// freopen("input", "r", stdin);
while (scanf("%d %d", &n, &m)!=EOF) {
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
if (getfa(x) != getfa(y)) {
fa[getfa(x)] = y;
g[x].push_back(y);
g[y].push_back(x);
} else {
bz[x] = bz[y] = 1;
edge.push_back(make_pair(x, y));
}
}
tot = 0;
dfs(1, 0);
for (auto u:edge)
edge1[belong[u.first]].push_back(make_pair(belong[u.second], 1)), edge1[belong[u.second]].push_back(
make_pair(belong[u.first], 1));
ans = 1;
//assert(tot <= 300);
vector<vector<int> > f(tot, vector<int>(tot, 0));
for (int i = 1; i <= tot; i++)
for (auto u:edge1[i]) {
int v = calc(u.second, mod - 2);
if (i < u.first)ans = mul(ans, u.second);
f[i - 1][i - 1] = add(f[i - 1][i - 1], v), f[i - 1][u.first - 1] = sub(f[i - 1][u.first - 1], v);
}
f.pop_back();
for (int i = 0; i < f.size(); i++)
f[i].pop_back();
printf("%d\n", mul(det(f), ans));
edge.clear();
for (int i = 1; i <= n; i ++) edge1[i].clear(), g[i].clear(), bz[i] = 0, belong[i] = 0, deep[i] = 0;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 667ms, 内存消耗: 9556K, 提交时间: 2019-10-07 22:04:00
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<t;i++)
const int mod=1e9+7;
void add(int &a,int b)
{
a+=b;
if(a>=mod)a-=mod;
}
void sub(int &a,int b)
{
a-=b;
if(a<0)a+=mod;
}
int inv(int a)
{
return a == 1 ? 1 : 1LL * (mod - mod / a) * inv(mod % a) % mod;
}
int det(std::vector<std::vector<int>>& mat, int n)
{
int result = 1;
for (int j = 0; j < n; ++ j) {
int pv = j;
while (pv < n && mat.at(pv).at(j) == 0) {
pv ++;
}
if (j < pv) {
result = result * (mod - 1LL) % mod;
std::swap(mat.at(j), mat.at(pv));
}
result = 1LL * result * mat.at(j).at(j) % mod;
int inv_ = inv(mat.at(j).at(j));
for (int i = pv + 1; i < n; ++ i) {
if (mat.at(i).at(j) != 0) {
auto t = 1LL * inv_ * mat.at(i).at(j) % mod;
for (int k = j; k < n; ++ k) {
add(mat.at(i).at(k), mod - mat.at(j).at(k) * t % mod);
}
}
}
}
return result;
}
#define MAXNUM 111111
vector<int> inite[MAXNUM];
struct edge{int a,b,c;};
vector<edge> vv;
vector<vector<int>> mat;
int isused[MAXNUM], nsize;
int pos[MAXNUM],isok[MAXNUM],dis[MAXNUM],snext[MAXNUM];
void dfs(int now,int p,int d)
{
dis[now]=d;
isused[now]=1;int flag=0,co=0;vector<int> tmp;
for(int k:inite[now])
if(k!=p||flag)
{
if(k==now)continue;
if(isused[k]==1)vv.push_back({now,k,1}),isok[now]=isok[k]=1;
else if(isused[k]==0){
dfs(k,now,d+1),tmp.push_back(k);
if(snext[k])co++,snext[now]=snext[k];
}
}
else flag=1;
if(co>=2||isok[now]){
pos[now]=nsize;
snext[now]=now;
for(int k:tmp)if(snext[k]&&dis[k]>dis[now])vv.push_back({now,snext[k],dis[snext[k]]-dis[now]});
nsize++;
}
isused[now]=2;
}
int main()
{
int n,m,nowid=1;
while(scanf("%d%d",&n,&m)==2)
{
rep(i,1,n+1)inite[i].clear(),isused[i]=0,isok[i]=snext[i]=0;
vv.clear();
nsize=0;
int a,b;rep(i,1,m+1)scanf("%d%d",&a,&b),inite[a].push_back(b),inite[b].push_back(a);
if(m==n-1){printf("1\n");continue;}
dfs(1,1,1);
mat.clear();
mat.resize(nsize);
rep(i,0,nsize)mat[i].resize(nsize,0);
int multi=1;
for(edge &ee:vv)
multi=multi*1ll*ee.c%mod;
for(edge &ee:vv)
{
int k1=pos[ee.a],k2=pos[ee.b];
int xx=inv(ee.c);
add(mat[k1][k1],xx),add(mat[k2][k2],xx);
sub(mat[k1][k2],xx),sub(mat[k2][k1],xx);
}
printf("%d\n",det(mat,nsize-1)*1ll*multi%mod);
}
}
and
which denotes a road between cities
.