Hdu第八场 树形dp+基环树
2024-09-05 13:51:08
每个牌背面的数字朝正面的数字连一条有向边
则题目变为问你最少翻转多少次 能使得每个数字的入度不超过1
首先判断图中每个连通块是不是树或者基环树 因为只有树或者基环树能使得每个点的入度不超过1
判的话就直接判断边的数量与点的数量之间的大小关系如果边数<=点数则可行
对于树 我们进行两次dp 第一次dp出以一个点为根需要翻转的次数 第二次就可以转移出以每个点为根需要翻转的次数
对于基环树 我们先看环里面需要翻转的次数 再判断环之外需要翻转的次数 环之外的方向是确定的 很好判断
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
const ll mod = ;
ll powmod(ll a, ll b)
{
ll res = ;
a %= mod;
assert(b >= );
for (; b; b >>= )
{
if (b & )
{
res = res * a % mod;
}
a = a * a % mod;
}
return res;
}
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
// head const int N = ;
int n, m, u, v, T, mt[N], hs[N], _;
vector<PII> e[N];
VI vec[N];
int vis[N], f[N], se[N], q[N], dp[N], pre[N], deg[N], fa[N];
PII chke[N];
int find(int u)
{
return f[u] == u ? u : f[u] = find(f[u]);
}
void solve()
{
n = ;
T++;
rep(i, , m + )
{
scanf("%d%d", &u, &v);
if (mt[u] != T) //离散化
{
mt[u] = T, hs[u] = n++;
}
if (mt[v] != T)
{
mt[v] = T, hs[v] = n++;
}
u = hs[u];
v = hs[v];
chke[i] = mp(u, v); //记录每条边
}
rep(i, , n) //初始化
e[i].clear(), vis[i] = , f[i] = i, vec[i].clear(), se[i] = ;
rep(i, , m + )
{
u = chke[i].fi, v = chke[i].se;
f[find(u)] = find(v); //一个连通块的点属于一个father
e[u].pb(mp(v, i)); //建边 i为正表示该边是反向与原来相反
e[v].pb(mp(u, -i));
}
rep(i, , n) //把一个连通块的点放到father的vector中
vec[find(i)].pb(i);
rep(i, , m + )
{
u = chke[i].fi, v = chke[i].se;
se[find(u)]++; //统计每个连通块中边的数量
}
int ans = , ans2 = ;
rep(i, , n)
{
if (find(i) != i) //每个连通块只会枚举一次
{
continue;
}
if (se[i] > SZ(vec[i])) //如果边数大于点数 则不是基环树也不是树 答案不存在
{
puts("-1 -1");
return;
}
if (se[i] < SZ(vec[i]))
{
//如果是树的话 dp两次 第一次dp出以0为根的翻转次数 第二次dp出全部点的翻转次数
int s = 1e9, s2 = ;
dp[i] = ;
int t = ;
q[] = i;
fa[i] = -;
rep(j, , t)
{
u = q[j];
for (auto p : e[u])
{
int v = p.fi;
if (v != fa[u])
{
fa[q[t++] = v] = u, pre[v] = p.se > , dp[i] += pre[v];
}
}
}
rep(j, , t)
{
u = q[j];
if (pre[u] == )
{
dp[u] = dp[fa[u]] - ;
}
else
{
dp[u] = dp[fa[u]] + ;
}
}
rep(j, , t)
s = min(s, dp[q[j]]); //当前树所需要的最少翻转次数
rep(j, , t)
if (dp[q[j]] == s)
{
s2++; //统计有多少个方案数
}
ans = ans + s;
ans2 = (ll)ans2 * s2 % mod;
}
if (se[i] == SZ(vec[i])) //基环树
{
int s = ;
for (auto u : vec[i])
{
deg[u] = SZ(e[u]); //统计每一个点的出度
}
int t = ;
for (auto u : vec[i])
if (deg[u] == )
{
q[t++] = u;
}
rep(j, , t)
{
u = q[j];
for (auto p : e[u])
{
int v = p.fi;
if (deg[v] <= )
{
continue;
}
if (p.se < )
{
s++;
}
--deg[v];
if (deg[v] == )
{
q[t++] = v;
}
}
}
int rt = -;
for (auto u : vec[i])
if (deg[u] == )
{
rt = u;
break;
}
int pree = 1e9, cnt = , u = rt, s3 = ;
while ()
{
for (auto p : e[u])
if (deg[p.fi] == && p.se + pree != )
{
s3 += p.se < ;
cnt++;
pree = p.se;
u = p.fi;
break;
}
if (u == rt)
{
break;
}
}
s3 = min(s3, cnt - s3); //环中的翻转最少次数是确定的
s += s3; //环外的方向是确定的 环外需要翻转的次数加上环中翻转的次数
ans += s;
if (s3 == cnt - s3)
{
ans2 = ans2 * % mod;
}
}
}
printf("%d %d\n", ans, ans2);
}
int main()
{
for (scanf("%d", &_); _; _--)
{
scanf("%d", &m);
solve();
}
}
//Card Game
最新文章
- String 中去掉空格
- 到底应该选择那种Linux.NET的部署方式？
- 【LeetCode】241. Different Ways to Add Parentheses
- js函数前面写上分号的原因
- AD帐户操作C#示例代码（一）——导入用户信息
- Ubuntu 14.04/14.10下安装VMware Workstation 11图文教程
- Making the Grade_滚动数组&&dp
- jQuery 的append在ie下的兼容性
- java对象数组的概述和使用
- 企业为什么要实行ERP系统，它到底有什么好处呢？
- jQuery选择器的优点
- ubuntu 下 apt /apt-get command not found 命令找不到
- Spring Cloud Zuul网关 Filter、熔断、重试、高可用的使用方式。
- javascript 事件编程之事件（流，处理，对象，类型）
- pyothon学习笔记2-元组
- LeetCode-300.Longst Increasing Subsequence
- python基础-函数基本特性和用法
- Extjs TreePanel API详解
- QuestaSim 中文注释乱码
- 直接在apk中添加资源的研究