牛牛选路径(牛客)


感觉很像小时候玩的一个游戏《一笔成画》
保证图连通，每条边都经过奇数次，等价于每条边只经过一次
对于重边可以不考虑，1->3,3->1，再走回来就行了
发现路径是什么样的不重要，重要的是起点和终点
发现起点和终点的度数一定是奇数
起点最后会引出一条出边
终点最后会收回一条入边
且起点和终点可以互换
所以预处理每个点的度数，判断是否为奇数
特别的，如果所有的度数都为偶数，则构成一个环，只需要找到点权最小的即可
否则，起点和终点一定成双成对,有多少对起终点就有多少条路径
统计答案时：
设a 很容易证明ad+bc 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#ifdef _MSC_VER
#  include 
#  define __builtin_popcount __popcnt
#  define __lg log2
#endif
#define N 100010
#define M 200010
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define mod 998244353
using namespace std;
ll n, m, a[N], d[N],s[N],cnt,ans;
bool cmp(ll x, ll y) {
    return a[x] < a[y];
}
int main() {
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    for (ll i = 1; i <= m; ++i) {
        ll u, v;
        scanf("%lld%lld", &u, &v);
        d[u]^=1;
        d[v]^=1;
    }
    for (ll i = 1; i <= n; ++i)
        if (d[i])
            s[++cnt] = i;
    if (!cnt) {
        ll mi = INF;
        for (ll i = 1; i <= n; ++i)
            mi = min(mi, a[i]);
        printf("%lld\n", mi * mi % mod);
    }
    else {
        sort(s + 1, s + 1 + cnt, cmp);
        for (ll i = 1; i <= cnt / 2; ++i)
            ans = (ans + a[s[i]] * a[s[cnt - i + 1]] % mod) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}
图论奇技淫巧

相关

【奇技淫巧】嘿嘿

图论---网络流

数的重心(图论深搜)

【Git】git奇技淫巧

电子科技大学《图论及其应用》复习总结--第七章 图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

标签