【codeforces 789D】Weird journey
2024-08-31 07:18:31
【题目链接】:http://codeforces.com/problemset/problem/789/D
【题意】
给你n个点,m条边;
可能会有自环
问你有没有经过某两条边各一次,然后剩余m-2条边,每条边各2次的
遍历方案,有的话输出方案数
【题解】
/*
把每条边都复制一条相同的边;
然后问题就能转化为在2*m条边中,去掉两条边;
然后使得剩下的图能够进行一笔画(每条边都只经过一次)
则使奇点的个数为0或为2就好了;
考虑自环边和普通边;
对于普通边来说:
①如果删掉的两条普通边是不相邻的两条边;
那么会有4个点变成奇点->排除
②如果删掉的两条普通边是相邻的两条边
则x-y-z中x和z会变成奇点;y仍旧是偶点;
刚好形成了两个奇点->符合要求
③考虑两条不同的自环边,如果删掉之后
每条自环边的端点两边都是同一个点,则每个点度数都减少2;
则每个点还都是偶点->奇点个数为0->符合
④一条自环边和一条普通边
普通边两边的点都变成奇点
->自环边两边的点是同一个点那个点度数-2还是偶点;
->总共两个奇点
还是符合题意
综上只要考虑
自环边和自环边
相邻的普通边
自环边和普通边
3种情况
如果没有联通的话得输出0
这里的联通只考虑m条边中出现过的点哦;
只要那些点联通就可以了
【Number Of WA】
3
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e6+100;
int n,m,ltk;
int f[N];
LL zh,ptb,ans,bian[N];
bool bo[N];
int zbb(int x)
{
if (f[x]==x)
return x;
else
return f[x] = zbb(f[x]);
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf就别用了!
cin >> n >> m;
ltk = n;
rep1(i,1,n) f[i] = i;
rep1(i,1,m)
{
int x,y;
cin >> x >> y;
bo[x] = true,bo[y] = true;
if (x==y)
{
zh++;
continue;
}
ptb++;
bian[x]++,bian[y]++;
int r1 = zbb(x),r2 = zbb(y);
if (r1!=r2)
{
ltk--;
f[r1] = r2;
}
}
rep1(i,1,n)
if (!bo[i])
ltk--;
if (ltk!=1)
return cout << 0 << endl,0;
//自环和自环
ans+=zh*(zh-1)/2;
//自环和普通边
ans+=zh*ptb;
//相邻的普通边
rep1(i,1,n)
ans+=bian[i]*(bian[i]-1)/2;
cout << ans << endl;
return 0;
}
最新文章
- IOS第一天多线程-01pthread
- readonly=“readonly”与readonly=“true”
- bzoj1173: [Balkan2007]Point
- poj 1226
- URAL 1707. Hypnotoad&;#39;s Secret(树阵)
- 纳税服务系统【统计图Fusionchart】
- 【推荐】地推统计结算工具SDK,手机开发首选
- Spring中资源的加载ResourceLoader
- CF719E. Sasha and Array [线段树维护矩阵]
- T-SQL:开窗函数(十二)
- 潭州课堂25班:Ph201805201 爬虫基础 第三课 urllib (课堂笔记)
- Latex 三线表及设置列数
- P3811 乘法逆元
- MongoDB集群搭建之主从模式
- Spring MVC - MultipartFile实现文件上传(单文件与多文件上传)
- Linux&#160;CentOS下Python+robot&#160;framework环境搭建
- 51. N-Queens (Array; Back-Track, Bit)
- 【linux系列】vmware12pro安装centos7
- js 表
- [置顶]
 针对 CoordinatorLayout 及 Behavior 的一次细节较真
热门文章
- [ JavaScript ] JavaScript 实现继承.
- 创造HTTPS的是个神
- Android系统Recovery工作原理之使用update.zip升级过程分析(九)---updater-script脚本语法简介以及执行流程【转】
- B1045 糖果传递 数学
- 图结构练习—BFSDFS—判断可达性(BFS)
- 1961 躲避大龙(dfs)
- [Apple开发者帐户帮助]三、创建证书(2)创建开发者ID证书
- [Apple开发者帐户帮助]二、管理你的团队(2)更改团队成员角色
- Django基础必备三件套: HttpResponse render redirect
- Python 28 选课系统的讲解